On reading S, the program stops. On reading R, the program reads in an edge weig
ID: 3818077 • Letter: O
Question
On reading S, the program stops.
On reading R, the program reads in an edge weighted directed graph from file GRAPHinput.txt to build the adjacency lists, and waits for the next command. The file GRAPHinput.txt is a text file. The first line of the file contains two integers n and m, which indicates the number of vertices and the number of edges on the graph, respectively. It is followed by m lines, where each line contains three integers: u, v, and w. These three integers indicate the information of an edge: there is an edge pointing from u to v, with weight w. Please note that the vertices of the graph are indexed from 1 to n (not from 0 to n 1). On reading W, the program writes the graph information to the screen, and waits for the next command. The screen output format of W is as follows: The first line should contain two integers, n and m, where n is the number of vertices and m is the number of edges. It should be followed by n lines, where each of these n lines has the following format:
u : (v1 w1) (v2 w2) ... (vx, wx)
On reading P s t, the program runs Dijkstra’s shortest path algorithm to compute a shortest s-t path, and prints out the shortest path information from s to t to the screen, and waits for the next command. The screen output format of P s t is as follows: There are two lines. The first line contains an integer dist, which is the length of the shortest path computed. The next line contains the indexes of all vertices along the path direction, starting from src and ending with dest, in format of: s v1 v2 ... t
Explanation / Answer
Dijkstra’s algorithm:
This algorithm is used to find the shortest path from a single source vertex to all other vertices in the given graph.
Algorithm steps:
1) Create a set shortest path tree set that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph.
Initialize all distance values as INFINITE.
Assign distance value as ‘0’ for the source vertex , so that it is fixed first.
The set shortest path tree is set initially empty and distances assigned to vertices are {0, INF, INF, INF, INF, INF, INF, INF} where INF indicates infinite. Now pick the vertex with minimum distance value. The vertex 0 is picked, include it in shortest path tree is set. So shortest path tree is set becomes {0}. After including 0 to shortest path tree is set, update distance values of its adjacent vertices. Adjacent vertices of 0 are 1 and 7. The distance values of 1 and 7 are updated as 4 and 8. Following sub graph shows vertices and their distance values, only the vertices with finite distance values are shown. The vertices included in SPT are shown in green color.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.