1. Consider the following weighted graph. (a) Give the EDGES of the shortest pat
ID: 3762159 • Letter: 1
Question
1. Consider the following weighted graph. (a) Give the EDGES of the shortest path tree of the weighted graph in the order they would be output by Djikstra's shortest path algorithm starting at VERTEX V1. (Give an ordered list of edges. Do NOT just draw the shortest path tree.) (b) Give the EDGES of the shortest path tree of the weighted graph in the order they would be output by Djikstra's shortest path algorithm starting at VERTEX V4. (Give an ordered list of edges. Do NOT just thaw the shortest path tree.)Explanation / Answer
1.
a)
The ordered list of edges using v1 as starting vertex -using Djikstra’s algorithm.
Edges and corresponding weights are given as follows:
From vertex 1 to 2: (1, 2) weight-6
From vertex 1 to 3: (1, 2) weight -6, (2, 3) weight -7
From vertex 1 to 4: (1, 2) weight-6, (2, 3)-7, (3, 4) weight-3
From vertex 1 to 5: (1, 5) weight-7
From vertex 1 to 6: (1, 5) weight -7, (5, 6) weight -4
From vertex 1 to 7: (1, 2) weight -6, (2, 7) weight -9
From vertex 1 to 8: (1, 2) weight -6, (2, 7) weight -9, (7, 8) weight -6
From vertex 1 to 9: (1, 5) weight -7, (5, 9) weight -2
From vertex 1 to 10: (1, 5) weight -7, (5, 9) weight -2, (9,10) weigth-7
From vertex 1 to 11: (1, 5) weight -7, (5, 9) weight -2, (9,10) weigth-7,(10,11) weight-4.
From vertex 1 to 12: (1, 2) weight -6, (2, 7) weight -9, (7, 8) weight -6, (8, 12) weight-3.
Tree diagram for shortest path:
b)
The ordered list of edges using v4 as starting vertex -using Djikstra’s algorithm.
Edges and corresponding weights are given as follows:
From vertex 4 to 1: (4, 3) weight-3, (3, 2) weight-7, (2, 1) weight-6.
From vertex 4 to 2: (4, 3) weight-3, (3, 2) weight-7
From vertex 4 to 3: (4, 3) weight-3.
From vertex 4 to 5: (4, 7) weight-4 ,(6, 5) weight-4
From vertex 4 to 6: (4, 7) weight-4. (7, 6) weight -6
From vertex 4 to 7: (4, 7) weight-4.
From vertex 4 to 8: (4, 8) weight-8.
From vertex 4 to 9: (4, 7) weight-4. (7, 6) weight -6, (6, 9) weight -1
From vertex 4 to 10: (4, 7) weight -6, (7, 10) weight -2
From vertex 4 to 11: (4, 7) weight-4(7, 11) weight-3.
From vertex 4 to 12: (4, 8) weight-8, (8, 12) weight-3.
Tree diagram for shortest path:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.