Single-Source Shortest Paths Framework

Let $G = (V, E)$ be a directed graph with a weight function $w : E \to \mathbb{R}$ assigning a real number to every edge (weights may be negative unless stated otherwise). For a path $p = \langle v_0, v_1, \dots, v_k \rangle$, its weight is

Given a source vertex $s$, the shortest-path weight from $s$ to $v$ is defined as

The single-source shortest paths problem asks for $\delta(s, v)$ for every vertex $v \in V$, together with enough information to reconstruct an actual shortest path — not merely its length. Every algorithm that solves this problem, no matter how it is organized internally, produces the same two output arrays:

• Distance array $d[v]$: an estimate of $\delta(s, v)$, initialized to $\infty$ for all $v \ne s$ and to $0$ for $s$. A correct algorithm terminates with $d[v] = \delta(s,v)$ for every reachable $v$.
• Predecessor array $\pi[v]$: the vertex immediately before $v$ on the current best-known path from $s$, initialized to `NIL`. At termination, following $\pi$ pointers from any reachable $v$ back to $s$ traces out an actual shortest path.

The array $\pi$ implicitly defines a shortest-paths tree rooted at $s$: a tree containing exactly the edges $(\pi[v], v)$ for every reachable $v \ne s$, such that the unique tree path from $s$ to any $v$ is a shortest path in $G$. This tree is the natural generalization of the BFS tree from unweighted shortest paths — the same idea, but now weighted. The single primitive operation every SSSP algorithm uses to improve its estimates is called relaxing an edge $(u, v)$: check whether going through $u$ offers a cheaper route to $v$ than the current estimate, and if so, update. This operation is developed carefully — including its optimal-substructure justification — in Edge Relaxation and Optimal Substructure; here we treat it as the shared building block that different algorithms schedule differently.

The generic relaxation-based framework underlying Bellman-Ford, Dijkstra, and DAG shortest paths is: initialize the distance and predecessor arrays, then relax edges in some order until distances stabilize. The pseudocode below states this framework precisely, using an abstract subroutine `RELAX` that all subsequent algorithms reuse verbatim. ``` INIT-SINGLE-SOURCE(G, s): for each vertex v in G.V: d[v] = infinity pi[v] = NIL d[s] = 0 RELAX(u, v, w): // Try to improve the best known distance to v by routing through u if d[u] + w(u, v) < d[v]: d[v] = d[u] + w(u, v) pi[v] = u return true // an improvement occurred return false GENERIC-SSSP(G, w, s): INIT-SINGLE-SOURCE(G, s) while there exists an edge (u, v) that can still be relaxed: RELAX(u, v, w) return d, pi ``` This "generic" version is not an efficient algorithm by itself — it does not specify which edge to relax next — but every concrete algorithm is an instantiation of it:

• Bellman-Ford relaxes every edge in the graph, $|V|-1$ times, in arbitrary fixed order, then does one extra pass to detect negative cycles.
• Dijkstra's algorithm (for graphs with non-negative weights) always relaxes edges out of the vertex with the currently smallest tentative distance, using a priority queue.
• DAG shortest paths relaxes edges out of vertices in topological order, guaranteeing each vertex is finalized before its edges are used.

The framework guarantees the following loop invariant, which every specific algorithm must preserve: > Upper-bound invariant. At all times during execution, $d[v] \ge \delta(s, v)$ for every vertex $v$, and once $d[v] = \delta(s,v)$ it never changes again if no negative cycle affects $v$. Relaxation only ever decreases $d[v]$, and it only decreases it to a value that corresponds to the weight of an actual $s \to v$ path (namely, the path to $u$ via $\pi$, plus edge $(u,v)$). Since $\delta(s,v)$ is by definition the minimum over all such path weights, $d[v]$ can never be forced below $\delta(s,v)$ by a correct relaxation step. This is why the framework is monotone and safe: it can be applied in almost any order without producing wrong (too-small) answers, though the order determines how quickly it converges to the right (tight) answer.

Detecting the negative-cycle caveat

If the graph contains a cycle $C$ reachable from $s$ with total weight $w(C) < 0$, then any vertex on or reachable from $C$ has no well-defined shortest path: you can loop around $C$ arbitrarily many times, each time subtracting more weight, so

A correct SSSP framework must detect this situation rather than silently report a wrong finite number. The standard detection technique piggybacks on the relaxation framework itself: ``` BELLMAN-FORD(G, w, s): INIT-SINGLE-SOURCE(G, s) for i = 1 to |V| - 1: for each edge (u, v) in G.E: RELAX(u, v, w) // Negative-cycle check: after |V|-1 rounds, distances should be stable for each edge (u, v) in G.E: if d[u] + w(u, v) < d[v]: return "NEGATIVE-WEIGHT CYCLE REACHABLE FROM s" return d, pi ``` The check works because of a key fact proved in the correctness section below: if the graph has no negative cycle reachable from $s$, then $|V|-1$ full rounds of relaxing every edge are always enough to reach the fixed point $d[v] = \delta(s,v)$ for all reachable $v$. So if a further relaxation is still possible after round $|V|-1$, the only explanation is a negative cycle.

Correctness of the framework in general. The upper-bound invariant $d[v] \ge \delta(s,v)$ holds throughout execution by induction on the number of relaxations performed: initially $d[s] = 0 = \delta(s,s)$ and $d[v] = \infty \ge \delta(s,v)$ for all other $v$; each relaxation of edge $(u,v)$ sets $d[v] \leftarrow d[u] + w(u,v)$, and by the inductive hypothesis $d[u] \ge \delta(s,u)$, so the new $d[v]$ is at least $\delta(s,u) + w(u,v) \ge \delta(s,v)$ (since appending edge $(u,v)$ to any path to $u$ gives some path to $v$, and $\delta(s,v)$ is the minimum over all such paths). This shows $d[v]$ never drops below the true shortest-path weight.

When does $d[v]$ reach $\delta(s,v)$ exactly? This requires that the specific algorithm's relaxation order eventually processes every edge of some shortest path to $v$, in order from $s$ outward. This is precisely the substance of the "path relaxation" lemma proved constructively in Edge Relaxation and Optimal Substructure; the short version is that if $\langle s = v_0, v_1, \dots, v_k = v\rangle$ is a shortest path and edges $(v_0,v_1), (v_1,v_2), \dots$ are relaxed in that relative order (not necessarily consecutively), then after all of them $d[v] = \delta(s,v)$.

Why $|V|-1$ rounds suffice when there is no negative cycle. Any shortest path (if it exists and the graph has no negative cycle reachable from $s$) can be taken to be simple — it never repeats a vertex, because removing a cycle from a path only decreases or preserves its weight when all cycles are non-negative, and strictly helps correctness to remove it. A simple path in a graph on $|V|$ vertices has at most $|V|-1$ edges. Bellman-Ford's outer loop relaxes all edges once per round; by induction, after round $i$, every vertex whose shortest path uses at most $i$ edges has $d[v] = \delta(s,v)$. After $|V|-1$ rounds, every simple shortest path — having at most $|V|-1$ edges — has been fully processed, so all reachable $d[v]$ values are exact.

Why one more round detects a negative cycle. If, after $|V|-1$ rounds, some edge $(u,v)$ still admits $d[u] + w(u,v) < d[v]$, then $d[v]$ was not the true fixed point — but we just argued $|V|-1$ rounds always suffice in the negative-cycle-free case. So the only way an $|V|$-th relaxation can still improve something is that the "shortest paths" involved are not simple (they can be shortened indefinitely by looping), which happens exactly when a negative cycle is reachable from $s$ and can reach $v$.

Complexity. Bellman-Ford performs $|V|-1$ rounds, each relaxing all $|E|$ edges, plus one final check pass:

Space is $O(|V|)$ for the $d$ and $\pi$ arrays (plus $O(|V| + |E|)$ to store the graph itself). This is the general-purpose cost when weights may be negative and the graph is not a DAG; specialized structure (non-negative weights, or acyclicity) allows strictly faster algorithms, which is exactly the motivation for DAG Shortest Paths (achieving $O(|V|+|E|)$ via topological order) and Dijkstra's algorithm (achieving $O(|E| + |V|\log|V|)$ with a binary-heap priority queue, when weights are non-negative).

Honesty about tradeoffs. Bellman-Ford's generality is its main appeal — it tolerates negative edges and detects negative cycles — but it pays for this with a quadratic-ish running time in dense graphs. Dijkstra is faster but silently wrong if given negative weights (it may finalize a vertex's distance before seeing a cheaper negative-weight route later). DAG shortest paths is the fastest of all but only applies when the input truly has no cycles. Choosing among them is a matter of matching the algorithm's assumptions to the graph at hand, not always reaching for the most general tool.

Consider a small currency-arbitrage-style graph with weights representing costs (negative weights allowed), source $s$: ``` Vertices: s, A, B, C Edges (u, v, weight): (s, A, 6) (s, B, 4) (B, A, -3) (A, C, 2) (B, C, 5) (C, A, 1) ``` There is no negative cycle here ($A \to C \to A$ has weight $2 + 1 = 3 \ge 0$). Trace Bellman-Ford, relaxing edges in the fixed order listed above, for $|V| - 1 = 3$ rounds.

Initialization: $d[s]=0,\ d[A]=d[B]=d[C]=\infty$, all $\pi = \text{NIL}$.

Distances stabilize after round 1 in this example (subsequent rounds confirm no further improvement, satisfying the theoretical guarantee of at most $|V|-1=3$ rounds). Final result:

Reconstructing the shortest path to $C$: follow $\pi[C]=A \to \pi[A]=B \to \pi[B]=s$, giving path $s \to B \to A \to C$ with weight $4 + (-3) + 2 = 3$, matching $d[C]$. Note this path has more edges than the direct-looking $s \to A \to C$ (weight $6+2=8$), illustrating why "shortest" means minimum total weight, not minimum edge count — the crucial difference from unweighted BFS shortest paths.

Negative-cycle case. Now add edge $(C, B, -10)$ to the same graph. The cycle $B \to A \to C \to B$ has weight $-3 + 2 + (-10) = -11 < 0$ and is reachable from $s$. Running the final check pass after $|V|-1$ rounds, edge $(C,B,-10)$ will still satisfy $d[C] + (-10) < d[B]$ no matter how the rounds settle, so Bellman-Ford correctly reports "negative-weight cycle reachable from $s$" instead of returning a finite (and wrong) distance array.

The shortest-paths framework, though presented here as one unified idea, emerged from several independent lines of research in operations research and early computer science, each solving a version of the routing and scheduling problems that motivate this article.

Every internet router running a distance-vector routing protocol (such as early RIP) is essentially executing a distributed, iterative relaxation process resembling Bellman-Ford, where each router refines its estimate of the shortest path to every destination based on advertisements from its neighbors — and network engineers must carefully avoid configurations that create negative "cost" cycles (or the routing analogue, count-to-infinity problems). Modern GPS and mapping services solve enormous SSSP instances continuously, using specialized variants (bidirectional search, contraction hierarchies, A*) that are all still built on the relaxation invariant described here. Financial arbitrage detection literally uses the negative-cycle detection in this framework: taking the negative logarithm of currency exchange rates turns "find a profitable trading loop" into "find a negative-weight cycle," directly reusing Bellman-Ford's final check pass as a fraud- or opportunity-detection tool. Compilers and build systems that must schedule tasks with weighted dependencies, and robotics motion planners computing cost-optimal paths through a configuration space, rely on the same $d$/$\pi$ output contract described in this article — regardless of which specific relaxation-ordering algorithm produces it.

:::quiz[What does the predecessor array $\pi[v]$ represent once an SSSP algorithm terminates correctly?]

• The vertex with the globally largest distance from the source
• The immediate predecessor of $v$ on a shortest path from the source ✓
• A vertex chosen arbitrarily during graph traversal
• The vertex farthest from $v$ in the graph

Ask the tutor: How does the choice of relaxation order in Dijkstra's algorithm let it avoid ever needing to "undo" a finalized distance, and why does that same guarantee break down with negative edge weights?