function floydWarshall(graph: Graph) {const n = graph.nodes.length;
const distance = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));for (const edge of graph.edges) distance[edge.from][edge.to] = edge.weight;
for (let pivot = 0; pivot < n; pivot++) { for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) {if (distance[i][pivot] + distance[pivot][j] < distance[i][j]) distance[i][j] = distance[i][pivot] + distance[pivot][j];
}
}
}
return distance;
}
Start from the adjacency matrix: 0 on the diagonal, the edge weight where an edge exists, ∞ elsewhere.
Understanding Floyd-Warshall
The idea
Floyd-Warshall computes the shortest distance between every pair of nodes at once, in a matrix. It adds the nodes one at a time as allowed intermediates: after pivot k, the cell [i][j] holds the shortest path from i to j that only passes through the first k nodes. The update is one line: if going through k is shorter, take it.
That is dynamic programming over the set of allowed intermediates, and the matrix can be updated in place. n³ steps is a lot, but for a few hundred nodes it is simpler and often faster than running Dijkstra from every node, and it takes negative edges in its stride.
The four stages
Complexity
Versus its siblings
Pseudocode
FLOYDWARSHALL(graph)
dist[i][j] ← weight of edge i → j, 0 on the diagonal, ∞ elsewhere
for each pivot k
for each i, for each j
dist[i][j] ← min(dist[i][j], dist[i][k] + dist[k][j])
return dist
When to use
Pitfalls
History
Bernard Roy published it in 1959 for transitive closure, Stephen Warshall in 1962 for Boolean matrices, and Robert Floyd the same year for shortest paths; the three-nested-loop form is Peter Ingerman's. It is the standard example of dynamic programming on graphs in every algorithms course.