Lab 9

Warning

To compile you should use a CMakeLists.txt. It takes sometimes to get use to it, but it makes the compilation much easier.

• In this lab, you can use the graph representation that you wish.

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.

Shortest-Path Algorithms

• In this part you will implement Breadth-First Search and Dijkstra’s algorithms.

Breadth-First Search

• If the graph you are using is weighted, do not consider the weights.

• Use the pseudocode given during the lecture.

Dijkstra’s Algorithm

• Implement the algorithm.

• This algorithm is more complex, so do not hesitate to put it on paper first.