Dijkstra meets a negative edge
A directed graph has edges (with weights)
S→A 6, S→B 2, S→D 9, A→C −5, B→C 3, B→E 7, C→E 2, C→T 6, D→T 1, E→T 2.
You run textbook Dijkstra from S: repeatedly extract the unfinished vertex with the smallest tentative distance, mark it final, and relax its edges only into vertices that are not yet final. By how much does Dijkstra's reported distance to T exceed the true shortest distance?
Show hints (2)+
- Track the order in which vertices become final.
- When A is finally extracted, can its −5 edge still help C?
Answer
Reveal answer →Final answer
4
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading