From \\ To 1 2 3 4 5 1 0 6 4 2 2 0 3 3 2 0 3 4 1 0 7 5 0 Steps involved in Dijks
ID: 373552 • Letter: F
Question
From To
1
2
3
4
5
1
0
6
4
2
2
0
3
3
2
0
3
4
1
0
7
5
0
Steps involved in Dijkstra’s Algorithm
The initial set called sptSET is empty and distances to vertices are {0, , , , , , } , indicates infinity.
Start with Vertex 1, as we have to find the shortest path from 1 to all other nodes. Start from node 1, and pick the shortest distant vertex, which is 4. Now sptSET becomes {0,2}
Therefore, the shortest distance from 1 to 4 is 2 and the shortest path is 1-4
Again pick the vertex with shortest distance, which is not in sptSET . the next shortest distant vertex is 3, sptSET becomes {0, 2, 3}
Therefore, the shortest distance from 1 to 3 is 3 and the shortest path is 1-4-3
The next minimum distance vertex is 2, sptSET becomes {0, 2, 3, 5}.
Therefore, the shortest distance from 1 to 2 is 5 and the shortest path is 1-4-3-2
The next minimum distance vertex is 5, sptSET becomes {0, 3, 4, 5, 6}.
Therefore, the shortest distance from 1 to 5 is 6 and the shortest path is 1-4-3-5
From To
1
2
3
4
5
1
0
6
4
2
2
0
3
3
2
0
3
4
1
0
7
5
0
Explanation / Answer
120 points] Find the shortest paths from node 1 to all ther nodes by Dijkstra's algorithm. (numbers on arcs are the lengths, and you need to show your steps to receive credits) 2. 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.