Floyd-Warshall

O(V³)

Floyd-Warshall computes shortest paths between all pairs of vertices in one sweep. It keeps a distance matrix — dist[i][j] starts as the direct edge weight (∞ if none, 0 on the diagonal) — and considers each vertex k in turn as a possible intermediate stop: if going i → k → j beats the current dist[i][j], it takes that. After every vertex has had its turn as the middle of a path, the matrix holds every shortest distance. The triple loop runs in O(V³), which beats running a single-source algorithm from every vertex on dense graphs, and it tolerates negative edges (though not negative cycles). The graph shows the current intermediate k and the endpoints; the table shows the distances filling in.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
DP table
Press ▶ to run
Edit the input and press Play

How it works

  1. Seed the matrix with direct edge weights (∞ for no edge, 0 on the diagonal).
  2. Pick the next vertex k as a candidate intermediate stop.
  3. For every pair (i, j), check whether i → k → j is shorter than the current best.
  4. If so, update dist[i][j]. After every k, the matrix holds all shortest distances.

Pseudocode

1floydWarshall(graph):               # O(V³)2  dist[i][j] ← edge weight, or ∞, 0 on the diagonal3  for each intermediate vertex k:4    for each pair (i, j):5      if dist[i][k] + dist[k][j] < dist[i][j]:6        dist[i][j] ← dist[i][k] + dist[k][j]   # route via k7  dist now holds every shortest distance