Skip to main content

Shortest Paths as Dynamic Programs

Shortest-path algorithms share the relaxation operation

d[v]←min⁡(d[v],d[u]+w(u,v)),d[v] \leftarrow \min(d[v], d[u] + w(u,v)),

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. Each pass extends known paths by one edge.
  • 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:

Always specify directedness, edge-weight restrictions, source scope, and the meaning of negative cycles before selecting a recurrence.

Source​