Dijkstra's algorithm

Greedy EXTRACT-MIN + RELAX for nonnegative weights, O((V+E) lg V) with a heap. Knows the negative-edge counterexample.

Dijkstra: greedy shortest paths for nonnegative weights

Dijkstra solves single-source shortest paths when all edge weights are $\geq 0$ , and it is faster than Bellman-Ford. It maintains a set $S$ of vertices whose final distance is known and a min-priority queue $Q$ keyed by v.d:

INITIALIZE-SINGLE-SOURCE(G, s); insert all vertices into $Q$ .
While $Q \neq = \emptyset$ : u = EXTRACT-MIN(Q); add $u$ to $S$ ; relax every out-edge $(u, v)$ , calling DECREASE-KEY when v.d drops.

Each vertex is extracted once, and at that moment its distance is final. With a binary heap: $∣ V ∣$ extractions and $\leq ∣ E ∣$ key decreases at $O (l g V)$ each give $O ((V + E) l g V) = O (E l g V)$ . A linear array scan gives $O (V^{2})$ (best for dense graphs); a Fibonacci heap gives $O (V l g V + E)$ .

Worked correctness (the squeeze)

When $u$ is extracted, let $y$ be the first vertex not in $S$ on a shortest $s ⇝ u$ path, and $x \in S$ its predecessor. When $x$ entered $S$ we relaxed $(x, y)$ , so $y . d = δ (s, y)$ (convergence). Then $δ (s, y) \leq δ (s, u) \leq u . d \leq y . d = δ (s, y),$ where: $δ (s, y) \leq δ (s, u)$ because $y$ is on a shortest path to $u$ and all weights are nonnegative (a prefix is no longer than the whole); $δ (s, u) \leq u . d$ is the upper-bound property; $u . d \leq y . d$ because EXTRACT-MIN chose $u$ over $y$ . Everything is squeezed equal, so $u . d = δ (s, u)$ . $■$

Why negative edges break it — the counterexample

The chain $δ (s, y) \leq δ (s, u)$ relies on nonnegativity. With a negative edge, a longer path can be cheaper, and the greedy commitment is wrong. Concrete case: edges $s \to u$ (weight 2), $s \to v$ (weight 5), $v \to u$ (weight $- 4$ ). Dijkstra extracts $u$ first with $u . d = 2$ and freezes it — but the true shortest path is $s \to v \to u = 5 + (- 4) = 1$ . Use Bellman-Ford when weights can be negative.

Worked example

On the CLRS Fig 22.6 graph (all nonnegative; vertices $s, t, x, y, z = 0, 1, 2, 3, 4$ ) Dijkstra from $s$ gives distances $[0, 8, 9, 5, 7]$ .

Dijkstra on the exercise graph (s, t, x, y, z = 0–4) after extracting s and then y. S = {s, y} is settled; the highlighted edges are the three just relaxed out of y, which pulled t to 8, z to 7 and x to 14. The next EXTRACT-MIN takes z (d = 7) — and by the squeeze argument that 7 is already final.

Why nonnegativity is a premise. Dijkstra extracts u first with u.d = 2 and never revisits it, but the route s→v→u costs 5 + (−4) = 1. The negative edge breaks δ(s,y) ≤ δ(s,u) in the squeeze — a longer path is now cheaper — so the greedy commitment is simply wrong. Reach for Bellman-Ford instead.