From Mohammed J. Zaki

IntroAlgorithms: Lab6

Lab 6: Dijkstra's Algorithm, Due: Wed, 28nd March, During Lab

In this lab you will implement dijkstra's shortest path algorithm as described in Fig 4.8. You can use the HeapDict priority queue implementation that works like a dictionary, and supports both insert and decrease key operations by simply setting the dictionary key to a given value. It also supports the delete min operation via popitem.

Your script should take a input a graph with weights, and a starting vertex \(v\), and it should output the shortest path length from \(v\) to all vertices in the graph, and you should also output the short path as a list of vertices (using the prev pointers in Fig 4.8).

The input graph will be specified as a pair of edges and weights; the example graph shown in Fig 4.9 is available as: Attach:example.txt.

For example, the first line 1 2 4 means that the directed edge (1,2) has weight 4.

The output should be as shown in Fig 4.9 when called with 1 as the source node, as follows:
1: 0, [ 1 ]
2: 3, [ 1,4,2 ]
3: 5, [ 1,4,2,3 ]
4: 2, [ 1,4 ]
5: 6, [ 1,4,2,5 ]
The format per line is vertex id: distance from \(v\), shortest path from \(v\)

Test your code on the following dataset: Attach:rome99.txt. This graph contains a large portion of the directed road network of the city of Rome, Italy, from 1999. The graph contains 3353 vertices and 8870 edges.

Retrieved from
Page last modified on March 22, 2018, at 08:55 PM