Why Weighted Shortest Paths Need New Techniques
Breadth-first search, discussed earlier in this series, finds shortest paths by counting edges, which works perfectly when every edge has the same implicit weight of 1. When edges have different weights, representing distances, costs, or times, a different approach is needed, and the possibility of negative edge weights introduces genuine complications that BFS never had to consider.
The Core Technique: Relaxation
Every shortest-path algorithm in this article builds on the same fundamental operation, Relaxation: for an edge (u, v) with weight w, check whether going through u offers a shorter path to v than the best path currently known, and if so, update v's recorded distance and predecessor.
RELAX(u, v, w):
if v.d > u.d + w(u, v):
v.d = u.d + w(u, v)
v.p = uEvery vertex begins with d = infinity (except the source, which starts at 0), and algorithms differ primarily in the order in which they apply relaxation across the graph's edges.
The Bellman-Ford Algorithm: Handling Negative Weights
Bellman-Ford is the more general algorithm, working correctly even when edge weights are negative, and it can additionally detect the presence of a Negative-Weight Cycle reachable from the source — a situation where shortest paths are not even well-defined, since one could loop around the negative cycle indefinitely to make the path arbitrarily short.
BELLMAN-FORD(G, w, s):
INITIALIZE-SINGLE-SOURCE(G, s)
for i = 1 to |G.V| - 1:
for each edge (u, v) in G.E:
RELAX(u, v, w)
for each edge (u, v) in G.E:
if v.d > u.d + w(u, v):
return FALSE // negative-weight cycle detected
return TRUEThe algorithm simply relaxes every edge in the graph, repeated |V| - 1 times. This number of repetitions is not arbitrary: a shortest path in a graph with V vertices can have at most V-1 edges (assuming no negative cycles, since a path visiting a vertex twice could not be shortest), so after V-1 rounds of relaxing every edge, every shortest path is guaranteed to have been fully propagated, regardless of which order the edges were considered in.
Detecting Negative Cycles
The final loop checks whether any edge could still be relaxed after the V-1 rounds. If so, this means some path is still improving after more edges than any acyclic shortest path could possibly need, which is only possible if a negative-weight cycle exists somewhere reachable from the source.
Since the algorithm performs V-1 rounds, each examining every edge, Bellman-Ford runs in O(VE) time — noticeably slower than the algorithms that follow, but necessary whenever negative weights might be present.
Dijkstra's Algorithm: Faster, But No Negative Weights Allowed
When all edge weights are guaranteed non-negative, Dijkstra's Algorithm offers a significantly faster solution by processing vertices in a specific greedy order, using the priority queue structure discussed earlier in this series regarding heaps.
DIJKSTRA(G, w, s):
INITIALIZE-SINGLE-SOURCE(G, s)
S = empty set // vertices whose final distance is determined
Q = priority queue containing all vertices, keyed by .d
while Q is not empty:
u = EXTRACT-MIN(Q)
S = S ∪ {u}
for each v in Adj[u]:
RELAX(u, v, w) // this may DECREASE-KEY on v in QThis structure is closely related to Prim's algorithm for minimum spanning trees, discussed earlier in this series, differing mainly in what value is being tracked and minimized (total distance from the source, rather than a single edge's weight).
Why Non-Negative Weights Are Essential for Correctness
Dijkstra's correctness relies on a greedy claim: once a vertex is extracted from the priority queue (added to S), its distance value is guaranteed to be its true shortest distance and will never need to be updated again. This claim depends critically on non-negative weights: if a negative edge existed, a path through a vertex not yet in S could potentially still produce a shorter path to an already-finalized vertex, violating the greedy assumption entirely. This is exactly why Dijkstra's algorithm produces incorrect results if given negative edge weights, without any warning that anything has gone wrong.
Analyzing the Running Time
Using a binary heap for the priority queue:
V calls to EXTRACT-MIN, each costing O(log V)
E calls to DECREASE-KEY (via relaxation), each costing O(log V)
Total: O((V + E) log V)
Using a Fibonacci heap (mentioned earlier in this series
regarding minimum spanning trees):
DECREASE-KEY costs O(1) amortized instead of O(log V)
Total: O(V log V + E)The Fibonacci heap variant is asymptotically faster for dense graphs, though the binary heap version is simpler to implement and often faster in practice due to smaller constant factors.
Comparing the Two Algorithms
Bellman-Ford:
- Handles negative edge weights correctly
- Detects negative-weight cycles
- Running time: O(VE) — slower
Dijkstra's Algorithm:
- Requires all edge weights to be non-negative
- Cannot detect or handle negative cycles
- Running time: O((V+E) log V) or O(V log V + E) — fasterIn practice, Dijkstra's algorithm is the default choice for shortest-path problems where negative weights are known not to occur, such as physical distances or non-negative costs, while Bellman-Ford is reserved for situations where negative weights are a genuine possibility, such as certain financial arbitrage detection problems where a negative cycle indicates a profitable trading loop.
Why Single-Source Shortest Paths Matter Across So Many Domains
These algorithms underlie GPS navigation systems computing driving directions, network routing protocols determining how data packets travel across the internet, and countless resource-allocation problems modeled as weighted graphs. The relaxation technique introduced in this article, along with the greedy structure of Dijkstra's algorithm and its close relationship to Prim's minimum spanning tree algorithm discussed earlier in this series, exemplifies how a small number of core algorithmic ideas recur across seemingly different graph problems.