Floyd-Warshall

Also known as: Floyd Warshall algorithm, All-pairs shortest paths

Floyd-Warshall computes all-pairs shortest paths on a weighted graph (positive or negative edges, no negative cycles) via dynamic programming: allow paths that may use intermediate nodes ${1,\ldots,k}$ and update a dense distance matrix.

Time $\Theta(V^3)$, space $\Theta(V^2)$. Simple to code; fine for dense graphs with hundreds of nodes. For sparse graphs and few sources, repeated Dijkstra (nonnegative) or Bellman-Ford is usually better.

← Back to CS Glossary