# Week 13 - 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 Make sure to have the activities signed off regularly to ensure progress is tracked. Download the provided project and open it in CLion. **NOTE**: in this week you will have to reuse the code of last week. Follow the instructions given in the `main.cpp` file. ### Activity 1: Find the shortest distance ADGKLPQ=16 ### Activity 2: Time to relax ```c++ bool shortest_paths::relax(const string &vertex, const graph::edge &edge) { } ``` Record your answer here ### Activity 3: Depth-first traversal Record your answer here ### Activity 4: Scanning all vertices ```c++ void shortest_paths::scan_all(std::vector<std::string> vector, bool reversed) { } ``` ### Activity 5: Shortest paths in acyclic graphs Record your answer here ### Activity 6: Paying a visit only once Record your answer here ### Activity 7: Finding the next vertex to be scanned ```c++ bool shortest_paths::find_next_dijkstra(std::string &next) { } ``` ### Activity 8: Dijkstra using linear search ```c++ void shortest_paths::dijkstra_lin_search() { } ``` ### Activity 9: Time complexity of Dijkstra - linear search Record your answer here ### Activity 10: Using a vertex heap ```c++ void shortest_paths::dijkstra_heap() { } ``` ### Activity 11: Minimizing the number of scans ```c++ void shortest_paths::dijkstra_heap() { } ``` ### Activity 12: Dijkstra's worst-case time complexity - a closer look Record your answer here ### Activity 13: Negative edge weights Record your answer here ## Looking back ### What we've learnt Formulate at least one lesson learned. ### 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?