Shortest Paths

A shortest-path algorithm does not merely “pick the smallest edge.” It maintains path-backed upper bounds on unknown distances and improves them through relaxation. BFS, topological-order processing, Dijkstra, Bellman–Ford, and all-pairs dynamic programming differ mainly in which relaxation order is safe—and that safety comes from explicit graph and weight preconditions.

The most damaging mistakes are therefore contract mistakes: running Dijkstra with a negative edge, treating no edge as weight zero, declaring every query invalid because of an unreachable negative cycle, or reconstructing a path from stale predecessors. This entry develops the proofs that make those failures visible.

Define the optimization problem first #

Let $G=(V,E)$ be a directed graph with additive edge weights

$$w:E\to\mathbb R.$$

A walk $P=(v_0,v_1,\ldots,v_k)$ follows an edge $(v_{i-1},v_i)$ at each step and has weight

$$w(P)=\sum_{i=1}^{k}w(v_{i-1},v_i).$$

A path has no repeated vertices under the convention used here. Algorithms may manipulate walks, but when a finite optimum exists without a relevant negative cycle, there is a simple shortest representative: deleting a nonnegative repeated cycle cannot increase cost.

For source $s$, the distance to $v$ is

$$\delta(s,v)=\inf\{w(P):P\text{ is an }s\text{-to-}v\text{ walk}\}.$$

Three outcomes must stay distinct:

• unreachable: no walk exists, so $\delta(s,v)=+\infty$;
• finite optimum: at least one shortest path realizes a real-valued distance;
• unbounded below: reachable negative cycling can make walk costs arbitrarily small, so $\delta(s,v)=-\infty$ for affected targets and no finite shortest walk exists.

Direction matters. A path may use only the direction of its edges. Weights need not be geometric lengths: they may be any additive cost for which the algorithm’s comparison and arithmetic assumptions hold.

Optimal substructure and relaxation #

If a subpath of a shortest path were not shortest between its own endpoints, replacing it with a cheaper subpath would make the full path cheaper. This optimal substructure makes local improvement meaningful.

Maintain a tentative label $d[v]$ and predecessor $parent[v]$:

$$d[s]=0, \qquad d[v]=+\infty\quad(v\ne s).$$

Relax directed edge $(u,v)$ by checking

$$d[v] > d[u] + w(u,v). \tag{1}$$

If true, assign

$$d[v]\leftarrow d[u]+w(u,v), \qquad parent[v]\leftarrow u. \tag{2}$$

Do not add a weight to infinity in an implementation: first require that $d[u]$ is finite, or use arithmetic with a safe mathematical infinity.

The path-backed upper-bound invariant #

Initially, $d[s]=0$ is backed by the empty path and every other label is infinity. A successful relaxation extends the concrete path backing $d[u]$ with real edge $(u,v)$. Therefore every finite label remains the weight of an actual source-to-vertex walk. Whenever a finite optimum exists,

$$d[v]\ge\delta(s,v).$$

Relaxation can lower an overestimate; it cannot invent a value below the true optimum while the label remains path-backed. This is the central debugging invariant. If a reported distance has no predecessor path with the same edge sum, the implementation is inconsistent even if the number looks plausible.

At an optimum, every reachable edge obeys a triangle inequality:

$$\delta(s,v)\le\delta(s,u)+w(u,v).$$

Algorithms differ in how they reach a state where all relevant inequalities are satisfied and when a tentative label may be declared final.

Select by graph and weight preconditions #

This is a correctness table first, not a universal speed ranking. Actual complexity also depends on graph representation, priority queue, graph density, and requested output.

Equal weights reduce to BFS #

When every edge has the same cost $c\ge 0$, BFS still gives an optimum: if $c>0$, minimizing weight is the same as minimizing edge count, while if $c=0$, every reachable walk has weight zero. BFS proves that its first discovery of $v$ gives the minimum number of edges from $s$; multiplying that layer number by $c$ gives the shortest-path distance.

This article does not repeat the queue proof. The bridge is relaxation: a BFS discovery assigns $d[v]=d[u]+1$, and FIFO order ensures no later relaxation can improve it. Once weights differ, layer order no longer orders path cost, so FIFO alone loses its correctness argument.

DAG shortest paths: one safe pass #

In a directed acyclic graph, compute a topological order $v_1,\ldots,v_n$ and relax every outgoing edge of each vertex in that order. Negative edges are allowed because no edge returns to an already processed predecessor position.

Correctness is induction on the topological order. Before processing $v_i$, every path into $v_i$ ends with an edge from some earlier vertex. By the induction hypothesis those predecessor distances are final, and their outgoing edges have been relaxed. Thus every possible final edge into $v_i$ has already offered its candidate, so $d[v_i]=\delta(s,v_i)$. Relaxing its outgoing edges establishes the candidates needed later.

The cost is $\Theta(V+E)$ with adjacency iteration: one topological traversal plus one relaxation per edge. Applying the same one-pass idea to a cyclic graph has no proof; a later edge may improve a vertex whose outgoing edges were already processed.

Dijkstra: settle the minimum label #

Dijkstra’s label-setting algorithm assumes

$$w(e)\ge 0\qquad\text{for every edge }e.$$

Maintain a settled set $S$ and a min-priority queue keyed by tentative distance:

1. initialize labels and enqueue the source;
2. extract an unsettled vertex $u$ with minimum tentative label;
3. settle $u$—its label is now final;
4. relax every outgoing edge $(u,v)$ and update the queue;
5. repeat until the queue has no finite candidate.

Zero-weight edges are valid. Negative edges are what break the proof.

Why the minimum tentative label is final #

Suppose $u$ is the first vertex Dijkstra settles incorrectly. Take a shortest path from $s$ to $u$ and let $y$ be its first unsettled vertex at that moment; let $x$ precede $y$, so $x$ is settled. When $x$ was processed, relaxing $(x,y)$ ensured

$$d[y]\le\delta(s,x)+w(x,y)=\delta(s,y).$$

The path-backed invariant also gives $d[y]\ge\delta(s,y)$, hence $d[y]=\delta(s,y)$. Because the remaining suffix from $y$ to $u$ has nonnegative weight,

$$d[y]=\delta(s,y)\le\delta(s,u)<d[u].$$

But $u$ was extracted with the minimum tentative label, so $d[u]\le d[y]$—a contradiction. The nonnegative suffix is the exact point where the precondition enters.

Trace with duplicate queue entries #

Use edges

$$S\to A(4),\ S\to B(1),\ B\to A(2),\ A\to C(1),\ B\to C(5),\ C\to T(3),\ A\to T(7).$$

If the priority queue cannot decrease a key in place, push the improved pair again. On extraction, discard (u,key) when key != d[u] or $u$ is already settled. Without that stale-entry check, obsolete work can trigger repeated scans or incorrect callback behavior.

The predecessor chain gives

$$S\to B\to A\to C\to T$$

with cost $1+2+1+3=7$, exactly matching $d[T]$.

Complexity depends on both structures #

With adjacency lists and a binary heap, each vertex is extracted and each edge can cause a logarithmic queue update, giving

$$O((V+E)\log V).$$

For a reachable connected-scale graph this is often abbreviated $O(E\log V)$, but the assumptions should be stated. With a dense matrix and a simple array scan for the smallest unsettled label, Dijkstra takes $O(V^2)$. A different heap changes asymptotic queue operations and constant factors; there is no representation-free runtime.

Stopping a single-target query is safe when the target is extracted and settled, not merely when an edge first gives it a finite label.

The negative-edge counterexample #

Consider this directed graph:

flowchart LR
  S((S)) -->|"2"| A((A))
  S -->|"5"| B((B))
  B -->|"-4"| A
  A -->|"2"| T((T))
  B -->|"10"| T

After processing S, Dijkstra has A=2 and B=5. It settles A, assigns T=4, and may settle T before B. But the true best route is

$$S\to B\to A\to T$$

with cost $5-4+2=3$. Edge B→A(-4) crosses back into the settled region and makes the previously final label smaller. A particular negative-edge graph may coincidentally produce a correct run; the issue is that the label-setting algorithm has no correctness guarantee.

Bellman–Ford: correctness by edge count #

Bellman–Ford repeatedly relaxes every edge. Its proof tracks how many edges an optimal candidate may use.

In a clean dynamic-programming formulation, let $d_i[v]$ be the minimum weight of an $s$-to-$v$ walk using at most $i$ edges. Then

$$d_i[v]=\min\left( d_{i-1}[v], \min_{(u,v)\in E}\bigl(d_{i-1}[u]+w(u,v)\bigr) \right). \tag{3}$$

An in-place implementation may propagate farther within one pass depending on edge order, but after pass $i$ it has found at least every optimum with at most $i$ edges. Edge order can accelerate convergence; correctness does not depend on favorable order.

If a finite shortest path exists and no source-reachable negative cycle can improve it, choose a simple shortest path. It has at most $V-1$ edges. Therefore $V-1$ complete passes suffice. A pass with no successful relaxation permits safe early termination because every edge inequality is already satisfied.

Worst-case time with an edge list is

$$O(VE),$$

with $O(V)$ auxiliary distance/predecessor storage beyond the graph.

Stage-by-stage example #

Use edges

$$S\to A(4),\ S\to B(5),\ A\to C(3),\ B\to C(-4),\ C\to T(2),\ A\to T(8).$$

The conceptual DP stages are:

At two edges, B→C(-4) improves C to 1. At three, C→T(2) improves T to 3. The predecessor certificate is $S\to B\to C\to T$.

Negative cycles are scoped, not global #

After the $V-1$ simple-path bound, perform one more full edge scan. If a reachable edge can still improve a label, some improving walk repeats a vertex; the repeated segment contains a negative cycle. Predecessor links can be used to enter and extract a cycle witness: step backward $V$ times from an improved vertex to guarantee arrival inside the repeated region, then follow predecessors until a vertex repeats.

In the example, add C→A(-4). The cycle

$$A\to C\to A$$

has weight $3-4=-1$. It is reachable from S, so repeatedly traversing it lowers costs to A, C, and any vertex reachable afterward, including T.

The effect is not “all answers everywhere are invalid.” For a source-specific query:

1. the cycle must be reachable from the source to affect any source label;
2. a target must be reachable from that cycle to have distance $-\infty$;
3. an unreachable negative cycle in another component does not alter finite source distances.

An API may throw on detecting any source-reachable negative cycle, return the cycle, or propagate $-\infty$ only to affected vertices. State which contract is in force.

For an undirected weighted graph represented by traversable incidences in both directions, a reachable negative edge $\{u,v\}$ creates the closed walk $u\to v\to u$ with twice the negative weight. Under walk semantics this is a negative cycle. A problem restricted to simple paths is a different optimization problem and must not inherit the walk-based theorem silently.

Floyd–Warshall: all pairs by allowed intermediates #

Floyd–Warshall solves APSP with a dynamic program and can also expose negative cycles. For the finite-distance recurrence, fix a pair not affected by a negative cycle and number the vertices $1,\ldots,n$. Let

$$D^{(k)}[i,j]$$

be the minimum weight of an $i$-to-$j$ walk whose intermediate vertices are drawn only from $\{1,\ldots,k\}$. A best route either avoids vertex $k$ or passes through it:

$$D^{(k)}[i,j] =\min\left( D^{(k-1)}[i,j], D^{(k-1)}[i,k]+D^{(k-1)}[k,j] \right). \tag{4}$$

Initialize every entry to $+\infty$, then set

$$D^{(0)}[i,i]\leftarrow\min(D^{(0)}[i,i],0)$$

for every vertex and, for every edge $(u,v)$, set

$$D^{(0)}[u,v]\leftarrow \min(D^{(0)}[u,v],w(u,v)).$$

The minimum operations preserve the lightest parallel edge and also preserve a negative self-loop instead of overwriting it with zero.

There are $n$ stages, each inspecting $n^2$ ordered pairs, so time is $\Theta(V^3)$ and distance storage is $\Theta(V^2)$. The recurrence represents finite shortest distances only when no negative cycle can affect the pair under consideration. A next-hop or predecessor matrix supports path reconstruction but has its own update orientation.

For a concrete recurrence, take edges P→Q(3), P→S(10), Q→R(-2), Q→S(8), and R→S(4). Before allowing R, the best known P→S cost is 10. Because P→R costs $3-2=1$, stage R tests

$$\min(10,\ 1+4)=5$$

and records the route P→Q→R→S.

If after all stages $D[i,i]<0$, there is a negative closed walk from $i$ back to $i$; equivalently, $i$ can reach a negative cycle that can return to $i$. The diagonal is therefore a detection signal, not a finite shortest distance. Ordinary finite APSP values are then not meaningful for every pair that can reach and leave that cycle; detecting a negative diagonal is not the same as propagating complete $-\infty$ affected-pair semantics.

Johnson: sparse all-pairs through reweighting #

Johnson’s algorithm supports APSP on a sparse directed graph with negative edges but no negative cycle:

1. add a new super-source with zero-weight edges to every vertex;
2. run Bellman–Ford to obtain a potential $h(v)$ for each vertex and detect any negative cycle;
3. reweight each edge as

$$w'(u,v)=w(u,v)+h(u)-h(v);$$

4. run Dijkstra from each source using nonnegative $w'$;
5. convert distances back.

Potentials make reweighted edges nonnegative because Bellman–Ford distances satisfy

$$h(v)\le h(u)+w(u,v).$$

For any $s$-to-$t$ path, the potential terms telescope:

$$\sum w'(u,v)=\sum w(u,v)+h(s)-h(t).$$

Every $s$-to-$t$ path receives the same endpoint-dependent offset, so their ordering is preserved. Johnson is a candidate for sparse APSP, not a universal performance winner; its actual cost depends on the repeated Dijkstra implementation and representation.

Reconstruct paths as certificates #

For one predecessor per vertex:

1. reject the request if the target is unreachable or has no finite optimum;
2. follow parent[target] backward until the source;
3. guard against more than $V$ steps or repeated vertices;
4. reverse the sequence;
5. verify every recorded edge and sum its weights.

The sum must equal the reported distance within the declared numeric semantics. A cycle in a supposedly finite predecessor chain indicates stale updates, a negative-cycle condition, or corrupt state.

Shortest paths need not be unique. Equal relaxations may be ignored to return one deterministic path, or recorded as multiple predecessors to represent a shortest-path DAG. That is an output decision; the distance alone does not imply a unique tree.

Weight and numeric engineering #

The mathematical proof assumes exact ordered addition. Real implementations must define:

• how a missing weight attribute is handled—error or explicit default;
• how parallel edges are selected or preserved;
• how absence differs from a zero-weight edge;
• whether integer addition can overflow;
• how floating-point rounding and NaN affect comparisons;
• whether mutation during the run is forbidden.

Never let an infinity sentinel overflow when adding an edge. Never treat NaN as an ordinary weight: comparisons with it do not provide the total order the algorithms expect. With floating point, two mathematically equal path sums may differ by rounding order; exact equality and negative-cycle tolerances require a domain-specific policy rather than an arbitrary epsilon.

Shortest-path trees are not minimum spanning trees #

A shortest-path tree rooted at $s$ minimizes each root-to-vertex path. A minimum spanning tree minimizes the sum of selected tree-edge weights over the whole undirected graph. Those objectives differ.

Take triangle edges s–a(2), s–b(2), and a–b(1):

• a shortest-path tree from s uses both weight-2 spokes, total tree weight 4, and reaches each target at distance 2;
• an MST uses one spoke plus a–b(1), total tree weight 3, but its root-to-one-target route costs 3 instead of the graph’s direct distance 2.

The algorithms and cut properties for the second objective belong in Minimum Spanning Trees.

Failure diagnostics #

1. Is the query single-pair, single-source, or all-pairs, and what output is required?
2. Are direction, additive weight, zero, absence, and parallel-edge rules explicit?
3. Are all weights equal, nonnegative, or allowed to be negative? Is the graph a DAG?
4. Which invariant should make a label final: BFS layer, topological order, Dijkstra settlement, or pass count?
5. Are finite labels backed by real predecessor paths with matching sums?
6. Are stale priority-queue entries discarded?
7. Is a negative cycle reachable from the source, and can it reach the target?
8. Does complexity name the graph representation and priority queue?
9. Could numeric overflow, rounding, NaN, or a bad infinity sentinel violate comparisons?
10. Is someone optimizing total tree weight while asking for root-to-target distance, or vice versa?

Exercises #

1. Run Dijkstra on the positive example through settlement of T. List every stale queue entry and explain why it is safe to skip.
2. In the negative-edge counterexample, identify the exact step and inequality in the settling proof that fails.
3. Add edge T→B(-5) to the Bellman–Ford example. Determine whether a negative cycle exists and which vertices have distance $-\infty$ from S under walk semantics.
4. Give a graph with a negative cycle that is not reachable from source s. What should source-specific Bellman–Ford report under the scoped semantics described here?
5. Prove the Floyd–Warshall recurrence by splitting optimal walks according to whether they use intermediate vertex $k$.
6. For the Johnson reweighting equation, show algebraically that two $s$-to-$t$ paths preserve their weight ordering.
7. A graph uses an adjacency matrix and array-based Dijkstra. Derive its $O(V^2)$ cost without mentioning $E$.
8. Construct two different shortest paths with the same total weight and explain how a one-parent implementation chooses between them.