Exam-style question
Try this first
During a trace of Dijkstra’s algorithm, a vertex has a current tentative distance of 6. A route through the vertex currently being processed would give that vertex a distance of 9. What should happen to the tentative distance?.
- A.It should be changed to 9
- B.It should remain 6
- C.It should be changed to 3
- D.It should be changed to infinity
Model answer
What a good answer should say
- It should remain 6
Explanation
Why this works
The existing tentative distance of 6 is shorter than the newly calculated distance of 9, so it is not replaced.
Common mistake
No common mistake is linked to this question yet.