Shortest Paths

Every navigation app, every network router, every game pathfinder is solving the same problem: given a weighted graph, find the cheapest route from one place to another. BFS already solved this when every edge counts as one step. Now the edges carry weights (distances, times, costs), and we want to minimize the total weight along a path. This lesson builds the shortest-path toolkit from a single primitive shared by every algorithm in it.

The problem and its primitive

Every algorithm maintains two arrays. For each vertex $v$, an estimate $v.d$ is an upper bound on $\delta (s,v)$, always $\ge$ the true distance, shrinking toward it. A predecessor $v.\pi$ records the previous vertex on the best path found so far, forming a shortest-path tree. We initialize $s.d=0$ and $v.d=\infty$ for every other vertex.

The one operation that updates these estimates is relaxation: testing whether going through $u$ improves our route to $v$.

Relaxation never produces an estimate below the true distance, and it can only ever lower an estimate. Every shortest-path algorithm below is a different discipline for deciding which edges to relax, and in what order. Two facts make relaxation work: the triangle inequality$\delta (s,v)\le \delta (s,u)+w(u,v)$, and optimal substructure: any subpath of a shortest path is itself a shortest path.¹ The latter is what makes greedy and dynamic-programming approaches both viable.

One relaxation step looks like this. Before, $v$ believes its best route costs $9$; we test the edge $(u,v)$ of weight $3$ against $u$'s settled estimate $u.d=5$. Since $5+3=8<9$, the edge is a shortcut: $v.d$ drops to $8$ and $v.\pi$ is rewired to point back through $u$.

We will trace the algorithms on this small weighted digraph. Note the negative edge $a\to b$ of weight $-2$: it is harmless here (there is no negative cycle), but it is exactly the kind of edge that will break Dijkstra and force us toward a dynamic program.

Dijkstra's algorithm

When all edge weights are non-negative, we can be greedy. $\text{Dijkstra}$'s algorithm grows a set $S$ of vertices whose shortest distances are finalized. At each step it picks the non-finalized vertex $u$ with the smallest estimate $u.d$, finalizes it, and relaxes its outgoing edges. A min-priority queue keyed by $d$ supplies the next vertex.

Why the greedy choice is correct. Correctness is framed around a single loop invariant: at the start of each iteration of the while loop, every finalized vertex already holds its true distance, $\forall x\in S:x.d=\delta (s,x).$ It holds initially ($S=\left\{s\right\}$ and $s.d=0=\delta (s,s)$). The maintenance step is the crux of the argument: suppose finalizing $u$ were the first move to break the invariant. Then either $u.d$ is set too low or too high.

• Too low ($u.d<\delta (s,u)$) is impossible, because relaxation never drops an estimate below the true distance — every value of $u.d$ is the cost of some real $s⇝u$ walk.
• Too high ($u.d>\delta (s,u)$): let $\pi$ be a genuine shortest path from $s$ to $u$. Walking it from $s$ (which is in $S$), let $(x,y)$ be the first edge that leaves $S$ — so $x\in S$, $y\notin S$. By the invariant $x.d=\delta (s,x)$, and $(x,y)$ was relaxed when $x$ was finalized, so $y.d=\delta (s,x)+w(x,y)=\delta (s,y)$. Now $y$ sits on a shortest path to $u$, and because every weight is $\ge 0$, the rest of $\pi$ only adds cost: $\delta (s,y)\le \delta (s,u)\le u.d$. Hence $y.d\le u.d$, so $\text{Extract-Min}$ would have returned $y$, not $u$ — contradiction.

The non-negativity is doing all the work in that last inequality: it guarantees extending a path never decreases its cost, so the closest frontier vertex can be safely frozen. A single negative edge breaks $\delta (s,y)\le \delta (s,u)$, so the greedy commitment becomes unsound.

On a small non-negative digraph the finalization order is exactly nondecreasing in distance, which is the visible signature of the greedy invariant. Notice that $a$ is finalized at distance $3$ via the two-hop route $s\to b\to a$, beating the direct edge $s\to a$ of weight $4$ — the relaxation through $b$ fired before $a$ was ever extracted:

Running time. Like Prim, Dijkstra does $V$ $\text{Extract-Min}$ and up to $E$$\text{Decrease-Key}$ operations. A binary heap gives $O((V+E)\log V)=O(E\log V)$; a Fibonacci heap improves this to $O(E+V\log V)$.

Bellman-Ford as a dynamic program

Dijkstra breaks when edges can be negative — its greedy finalization assumes a finalized estimate can never improve, which negative edges violate. $\text{Bellman-Ford}$ trades speed for generality. It is best derived not as relax everything repeatedly but as a genuine dynamic program. That framing is worth keeping, because it explains where the $\left|V\right|-1$ comes from.

The subproblem. Bound the number of edges a walk may use. For each vertex $v$ and each budget $k$, define

The full answer we want is $\text{OPT}(n-1,v)$ for $n=\left|V\right|$, since (as we prove below) shortest paths never need more than $n-1$ edges.

The recurrence. A cheapest walk to $v$ using at most $k$ edges either uses at most $k-1$ edges already, or it takes one final edge $(u,v)$ after a cheapest $\le (k-1)$-edge walk to $u$. Minimizing over both:

with base cases $\text{OPT}(0,s)=0$ and $\text{OPT}(0,v)=\infty$ for $v\ne s$. This is exactly relaxation: filling row $k$ of the table from row $k-1$ is one full pass that relaxes every edge. The tabular form makes the layering explicit, with row $k$ holding the best walk of length $\le k$:

Why stop after $n-1$ rounds? This is the theorem that licenses the whole algorithm. If $G$ has no negative-cost cycle, then for all $s,t$ the distance $\delta (s,t)$ is achieved by a path of length $\le n-1$. The proof is a short-circuiting argument: any $s⇝t$ walk of length $>n-1$ visits some vertex twice, so it contains a cycle. Excising that cycle yields a shorter walk of cost no greater than the original (the removed cycle has non-negative cost). Repeating until no cycle remains leaves a simple path, with at most $n-1$ edges, that is no more expensive. So the rows of the DP stop changing by row $n-1$.

Saving space. The recurrence only ever reads row $k-1$, so we collapse the table to a single 1-D array $d[\cdot ]$ updated in place, recovering the familiar form of Bellman-Ford as $n-1$ rounds of relaxing every edge. Note negative edges are fine; only a negative cycle breaks the theorem.

Detecting negative cycles. After $n-1$ rounds, if any edge can still be relaxed, some walk was improved using $n$ edges — only possible if a negative cycle lets the cost descend without bound. So one extra pass is exactly the test: relax everything once more, and any successful relaxation certifies a negative cycle reachable from $s$² (where cheapest cost to reach a vertex is no longer even well-defined). Dijkstra entirely lacks that capability. The cost is $\Theta (V\cdot E)$: $\left|V\right|-1$ passes, each relaxing all $\left|E\right|$ edges.

Laid out as the DP table $\text{OPT}[k,v]$, the layering is plain: row $k$ holds the cheapest walk of at most $k$ edges, each row computed from the one above by a single full pass of relaxation. The entries that improved on each row are shaded; the table stops changing after row $2$, well within the $n-1=4$ bound:

Floyd-Warshall: all pairs at once

Sometimes we want $\delta (u,v)$ for every pair of vertices, a full distance matrix. Running Bellman-Ford from each source costs $O(V^{2}E)$, but $\text{Floyd-Warshall}$ does better with a slick dynamic program over intermediate vertices.

Number the vertices $1,\dots ,n$. Let $d_{ij}^{(k)}$ be the weight of the shortest path from $i$ to $j$ whose intermediate vertices all lie in $\left\{1,\dots ,k\right\}$. Either the shortest such path avoids vertex $k$ (then it is $d_{ij}^{(k-1)}$) or it routes through $k$, splitting into an $i\to k$ piece and a $k\to j$ piece, each using only earlier intermediates:

One round of the recurrence makes the mechanism concrete. Starting from $d^{(0)}$ — direct edges only — and admitting intermediates from $\left\{1,2\right\}$ produces $d^{(2)}$: the entry $d_{13}$ drops from $8$ to $5$ via $1\to 2\to 3$, and the once-unreachable $d_{42},d_{43}$ become finite by routing through vertex $1$ then $2$. The five matrices $d^{(0)},\dots ,d^{(4)}$ below trace one round per permitted intermediate; the entries that improved in each round are shaded:

Three nested loops over $k$, $i$, $j$ evaluate this recurrence directly: the outer loop admits one intermediate vertex $k$ per round (exactly the five matrices above), and the inner two relax every pair against a route through it.

This is $\Theta (V^3)$ time and $\Theta (V^2)$ space: compact, cache-friendly, and a clean win on dense graphs.³ It handles negative edges, and a negative entry on the diagonal ($d_{ii}<0$) flags a negative cycle.

Choosing an algorithm

The decision tree is simple: unweighted, use BFS; a DAG, relax in topological order; non-negative weights, use Dijkstra (the fastest for one source); negative edges possible, use Bellman-Ford and let it police negative cycles; every pair at once, use Floyd-Warshall. All five are, at heart, disciplined applications of the same $\text{Relax}$ primitive.

Takeaways

• Shortest paths rest on relaxation plus two structural facts: the triangle inequality and optimal substructure.
• $\text{Dijkstra}$ greedily finalizes the closest frontier vertex; correct only for non-negative weights, in $O(E+V\log V)$ with a Fibonacci heap.
• $\text{Bellman-Ford}$ is a dynamic program: $\text{OPT}(k,v)$ = cheapest $s⇝v$ walk of $\le k$ edges, and one DP row = one pass of relaxing all edges. Shortest paths need $\le \left|V\right|-1$ edges (short-circuit any cycle), so $\left|V\right|-1$ rounds suffice; one extra round detects negative cycles. Slower at $\Theta (V\cdot E)$ but handles negative edges.
• On a DAG, relaxing in topological order solves SSSP in $\Theta (V+E)$.
• $\text{Floyd-Warshall}$ computes all-pairs shortest paths in $\Theta (V^3)$ via a dynamic program over intermediate vertices.