Exam-style question
Try this first
Trace Dijkstra’s shortest path algorithm from A to D using the weighted graph with edges A-B = 4, A-C = 1, C-B = 2, B-D = 1 and C-D = 7. Show the important tentative distances as vertices are selected, and state the shortest route and its total distance.
Model answer
What a good answer should say
- Initially, A has distance 0 and B, C and D have no known distance.
- After processing A, B has tentative distance 4 and C has tentative distance 1.
- C is selected next because it has the smaller tentative distance.
- Processing C changes B to 3 and gives D a tentative distance of 8.
Explanation
Why this works
At each stage, the smallest available tentative distance is selected. Routes through the selected vertex are then checked to see whether they give shorter distances to connected vertices.
The route through C and B improves the route to D.
Common mistake
No common mistake is linked to this question yet.