COP 3503 Dijkstra Shortest Path

Implement Dijkstra's Algorithm on a graph supporting simple integer weights. Your input will consist of a number of vertices and a list of doubly-connected edges along with their costs; your output will consist of a simple representation of the Dijkstra spanning tree.

Sample Input/Output

Sample input for the graph from the slides:

6
5
9
1 2 4
1 5 3
2 3 2
2 4 9
2 5 8
3 4 1
4 5 5
4 6 3
5 6 7

Sample output for the same graph:

6
1 3 5
2 7 1
3 6 4
4 5 5
5 -1 -1
6 7 5

Specifics

• Use whatever collections from the standard Java library you wish.
• Your edges only need integer weights; your vertexes only need to be "named" by their implicit serial number.
• When you have a choice between two vertices, always choose the lower-numbered vertex.