Give a three-vertex weighted graph with a single negative edge on which Dijkstra's algorithm returns a wrong shortest path, state the wrong answer and the true one, and identify the exact step of the correctness proof that fails.

Give a three-vertex weighted graph with a single negative edge on which Dijkstra's algorithm returns a wrong shortest path, state the wrong answer and the true one, and identify the exact step of the correctness proof that fails.

Approach: Dijkstra finalises a vertex when it is popped. Build an instance where a cheaper route to a finalised vertex is discovered afterwards, and see which invariant that violates.

Take s to a with weight 1, s to b with weight 4 and b to a with weight -4, where Dijkstra reports the distance to a as 1 while the true distance is 0 along s, b, a. Dijkstra pops a at tentative distance 1 and finalises it, then pops b at 4 and the relaxation of b to a would lower a to 0, but a is already a finalised vertex and is never re-examined, so the reported figure stays 1. The correctness proof assumes that when a vertex is popped with the smallest tentative distance no undiscovered path can be shorter, which relies on every weight being non-negative so that extending a path leaves its cost at least as large. One negative edge destroys that monotonicity, so the greedy invariant fails at the moment of finalisation. Allowing a finalised vertex back into the queue restores the right answer at the cost of exponential worst case behaviour on adversarial graphs, which is why Bellman-Ford with its V - 1 rounds is the correct algorithm once any weight is negative.

Follow-up: What condition on the negative edges still lets Dijkstra run correctly after a reweighting step?

Key concepts: greedy invariant, negative edge, relaxation, finalised vertex.