5 1 2 9 1 3 12 2 4 18 2 3 6 2 5 20 3 5 12 0 0 0 1 5Your program should print the graph, followed by the shortest path from s to t and the distance from s to t via that path, in a reasonable format. The example input might lead to the following output.
There are five vertices. The edges are as follows. (1,3) weight 12 (1,2) weight 9 (2,5) weight 20 (2,3) weight 6 (2,4) weight 18 (3,5) weight 12 The shortest path from 1 to 5 has length 24 and is 1 -> 3 -> 5
Write your program in a clean way, with reasonably chosen functions. For this assignment, it is not necessary to have more than one module. But a single main program that does everything is unacceptable.
Use Dijkstra's algorithm. Here is a summary of how that algorithm works. s is the start vertex and t is the destination vertex.
Each vertex holds a current distance and a current next vertex. I will write dist(v) for the distance value of vertex v, and next(v) for the next vertex stored with v.
Each vertex has one of three status values: done, pending or peripheral.
A done vertex v has been finished, and dist(v) is the correct shortest distance from v to s. The shortest path from v to s begins by going to next(v).
A pending vertex v is adjacent (via an edge) to at least one done vertex, but is not done. Value dist(v) is the shortest distance from v to s, provided there is a restriction that the path taken from v to s must begin by going from v to a done vertex. Vertex next(v) is the done vertex to go to from v to get to s.
v ------> next(v) -----> ... --------> sNote that it is possible, for a pending vertex v, that there is a better way to get from v to s that starts by going to a different vertex, one that is not yet marked done.
A peripheral vertex is one that is neither done nor pending. Its dist and next values are meaningless. There is no edge between any done vertex and any peripheral vertex.
The algorithm begins by marking the start vertex s as done and setting its distance to 0. Each vertex v that is adjacent to s is marked pending, with dist(v) set to the weight of the edge between v and s. All other vertices are marked peripheral.
The algorithm then repeatedly does the following basic step, until vertex t is done, or there are no more pending vertices.
Be sure to make reasonable functions. Do not put all of the parts of Dijstra's algorithm in a single function.
When the algorithm is finished, you will be able to follow a path from t back to s by following the chain of next vertices.
t -----> next(t) -------> next(next(t)) ----> ... -----> sPrint that chain out backwards. The easiest way to do that is to use recursion. To print a path backwards, starting at vertex u, print the path starting at next(u) backwards, then print u.