Shortest Paths as Dynamic Programs
Shortest-path algorithms share the relaxation operation
but differ in the state dimension and the order in which relaxations become safe or complete.
Recurrence views
- Bellman–Ford can index state by the maximum number of edges allowed. In the layered recurrence, each new layer extends known paths by at most one edge; an in-place pass may propagate farther.
- Floyd–Warshall indexes state by the set of vertices allowed as intermediates.
- Shortest paths in a DAG follow a topological dependency order and require one pass of relaxations.
- Dijkstra uses a greedy settlement order enabled by nonnegative weights; it is better understood through its greedy invariant than as a table DP.
Algorithm selection
Use the graph-algorithm pages for the complete contracts:
- Dijkstra: single source, nonnegative edges.
- Bellman–Ford: single source, negative edges allowed.
- Floyd–Warshall: all pairs, cubic time and quadratic storage.
Always specify directedness, edge-weight restrictions, source scope, and the meaning of negative cycles before selecting a recurrence.
A DAG example and the extra state for cycles
In a directed acyclic graph (DAG), a topological order puts every edge's source before its destination. Set the source distance to zero, others to infinity, then relax outgoing edges in that order. For edges s→a:2, s→b:5, a→b:−4, order (s,a,b) first sets a=2 and b=5, then improves b to −2. Negative edges are harmless because there is no cyclic dependency. Topological sorting plus relaxation costs O(V+E). A cycle must be rejected, not silently processed with an incomplete topological order. The DFS topological-order example constructs that order, handles disconnected components, and rejects cycles. For weighted adjacency lists, pass its function the same vertices and neighbor IDs without their weights, then use the original weighted edges for relaxation.
For cyclic graphs, define D[k,v] as the cheapest walk from s to v using at most k edges. The base has D[0,s]=0 and all other entries infinite. Each new layer keeps D[k-1,v] or extends an incoming edge from D[k-1,u]. Separate arrays enforce exactly this layer meaning; in-place Bellman–Ford may propagate farther within one pass. The edge budget breaks the dependency cycle even when the input graph has cycles. A negative cycle makes only source-destination pairs that can traverse it unbounded below.