# 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?