Shortest Paths
Motivation
The single-source shortest-path problem — find the minimum-weight route from a fixed source to every reachable vertex in a weighted graph — underlies virtually every routing system in production: GPS navigation, internet packet forwarding, network analysis (Kleinberg and Tardos 2005; Cormen et al. 2009).
Two algorithms on this site solve it: Dijkstra’s algorithm handles the common case of non-negative weights efficiently; Bellman-Ford handles the general case with arbitrary real weights and detects when no finite solution exists. This article introduces the shared problem and the complications that distinguish them.
Problem
Let \(G = (V, E)\) be a directed graph with \(n = |V|\) vertices, \(m = |E|\) edges, and edge weights \(w : E \to \mathbb{R}\). Fix a source vertex \(s \in V\). The shortest-path distance from \(s\) to \(v\) is
\[ d(v) = \min_{P : s \leadsto v} w(P), \]
where the minimum ranges over all simple paths from \(s\) to \(v\) and \(w(P)\) is the sum of edge weights along \(P\). If no path reaches \(v\), then \(d(v) = +\infty\).
Relaxation
Every shortest-path algorithm maintains a distance estimate \(D[v]\) for each vertex — initialized to \(D[s] = 0\) and \(D[v] = +\infty\) for \(v \neq s\) — and repeatedly relaxes edges. Relaxing an edge \((u, v)\) asks whether the route to \(u\) followed by \((u, v)\) improves the current estimate for \(v\):
\[ D[v] \leftarrow \min\{D[v],\; D[u] + w(u, v)\}. \]
Relaxation can only decrease estimates, and it only sets a distance to the weight of an actual walk from \(s\). Algorithms differ in which edges they relax and in what order; correctness depends on relaxing enough edges in the right sequence.
Complications
Negative Edges
Negative edge weights are not inherently a problem. A path can include a negative edge and still have a well-defined, finite shortest-path distance.
There is no way to exploit the negative edge repeatedly: the graph has no cycle, so every path from \(s\) to \(t\) is traversed at most once.
Negative edges do, however, break one key property that makes Dijkstra fast: with non-negative weights, the cheapest unfinalized vertex cannot be reached more cheaply by any later path, so its distance can be committed to immediately. A negative edge downstream can always make an apparently expensive path competitive, so that local guarantee disappears.
Negative Cycles
A negative cycle is a cycle whose edge weights sum to less than zero. If such a cycle is reachable from \(s\), then any vertex reachable beyond it has no well-defined shortest-path distance: a walk can traverse the cycle arbitrarily many times, driving the total weight toward \(-\infty\).
Once a walk reaches \(a\), it can loop through the cycle \(r\) times for any \(r \geq 0\), reducing the total weight by \(r\). There is no minimum. A complete shortest-path algorithm must detect a reachable negative cycle and report it explicitly rather than returning a finite but meaningless answer.
Algorithms
No single algorithm dominates across all cases. The standard choices by graph type are:
| Graph | Algorithm | Time |
|---|---|---|
| Unweighted | BFS | \(\Theta(n + m)\) |
| Non-negative weights | Dijkstra | \(O(m \log n)\) |
| Arbitrary real weights | Bellman-Ford | \(\Theta(nm)\) |
| DAG, arbitrary weights | Topological relaxation | \(\Theta(n + m)\) |
| All-pairs, dense graph | Floyd-Warshall | \(\Theta(n^3)\) |