Dijkstra's algorithm

Dijkstra: greedy shortest paths for nonnegative weights

Dijkstra solves single-source shortest paths when all edge weights are $\ge 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:

1. INITIALIZE-SINGLE-SOURCE(G, s); insert all vertices into $Q$.
2. While $Q\ne\varnothing$: 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 $\le|E|$ key decreases at $O(\lg V)$ each give $O((V+E)\lg V)=O(E\lg V)$. A linear array scan gives $O(V^2)$ (best for dense graphs); a Fibonacci heap gives $O(V\lg V + E)$.

Worked correctness (the squeeze)

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

Why negative edges break it — the counterexample

The chain $\delta(s,y)\le\delta(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]$.