10. Graph Algorithm
In this lab, you can use the graph representation that you wish.
10.1. Topological Sort
In this first part, you need to implement the topological sort algorithm.
First, start creating an acyclic graph (you can use the graph from the course).
Then, implement one of the possible algorithms.
Test your code and make sure that you obtain a topological ordering of nodes.
10.2. Shortest-Path Algorithms
In this part you will implement Breadth-First Search and Dijkstra’s algorithms.
10.2.1. Breadth-First Search
If the graph you are using is weighted, do not consider the weights.
Use the pseudocode given during the lecture.
10.2.2. Dijkstra’s Algorithm
Implement the algorithm.
This algorithm is more complex, so do not hesitate to put it on paper first.
ENSURE WE HAVE RECORDED YOUR COMPLETION. FAILURE TO DO SO WILL RESULT IN A GRADE OF 0!