Skip to content
Get started

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)+
  1. Track the order in which vertices become final.
  2. When A is finally extracted, can its −5 edge still help C?

Answer

Reveal answer →

4

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions