---
# System prepended metadata

title: "Week\_14\_-\_More\_shortest\_paths"

---

# Week 14 - More shortest paths
  

## Team

  

Team name:

Date:

  

Members

  

| Role                                                                                                                                                                          | Name |

|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|

| \*\*Facilitator\*\* keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon.                                             |      |

| \*\*Spokesperson\*\* communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |      |

| \*\*Reflector\*\* observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |      |

| \*\*Recorder\*\* guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |      |

  

## Activities

  

### Activity 1: Applications of negative edges

  

- When you want to go from point a to be with losing as little money as possible. Then you can consider negative weights.

  
  

### Activity 2: Dijkstra on graphs with negative edges

  

The order is: a to c to b to e to d to f

The vertices c, d, e, f are not correct since they have a negative value. 

  

### Activity 3: Shortest paths trees

  

- No its not the shortest path possible.

- The distance from d and f can be further decreased

- In this case, the shortest path to d would come from vertex e (3-2+2+3 = 6). however , going to d over b would be smaller (3+1 = 4). However, b should have been relaxed already, and e to d should never have become "smallest"

  

### Activity 4: Do it yourself

  

- It takes 6 passes to go over the graph and find the distances.

- There are 36 relaxations.

  

### Activity 5: An easy graph

  

- a-b-c-d-e-f-g. Since all the vertices together, the order does not really matter.

  

### Activity 6: Worst-case number of passes

  

- The maximum amount of passes is: n

- The longest path, worst case is n-1. The shortest path tree has the height equal to the amount of vertices.

  

### Activity 7: Bellman-Ford

  

```c++

bool bellman_ford::relax_all(const std::vector<graph::vertex> &vector) {

  

 bool isChanged = false;

 for (const auto &v : vector) {

 if (relax(v)) {

            isChanged = true;

        }

    }

 return isChanged;

}

```

  

### Activity 8: Negative cycles

  

- Use it to calculate my savings which keep draining.

- 

  

### Activity 9: Negative cycles and shortest paths

  
  

### Activity 10: Bellman-Ford with negative cycle detection

```c++

void bellman_ford::compute(const graph::vertex &source) {

prepare(source);

for (int i = 0; i < m_graph.vertices().size()-1; i++) {

relax_all(m_graph.vertices());

}

m\_cycle\_found = relax_all(m_graph.vertices());

  

}

```

\[!\[Activity-10a.png\](https://i.postimg.cc/pX3svy9s/Activity-10a.png)\](https://postimg.cc/rKC1CVN4)

\[!\[Activity-10b.png\](https://i.postimg.cc/5tbq9zfS/Activity-10b.png)\](https://postimg.cc/87XrtjJ7)

  

### Activity 11: Worst-case time complexity of Bellman-Ford

- Worst case time-complexitiy is O(V*E) where V is vertices and E is edges

### Activity 12: Comparing algorithms

  

\[!\[Activity-12.png\](https://i.postimg.cc/662RXcdN/Activity-12.png)\](https://postimg.cc/MXwX0yPs)

  

## Look back

  

### What we've learnt

  

Fill in...

  

### What were the surprises

  

Fill in...

  

### What problems we've encountered

  

Fill in...

  

### What was or still is unclear

  

Fill in...

  

### How did the group perform?

  

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?
