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!