Pattern visualizer
Floyd Warshall Algorithm
Any shortest path from i to j either never touches vertex k, or it does — and if it does, it is exactly the shortest i-to-k path followed by the shortest k-to-j path, both already known once k has had its turn. So looping k from 0 to n-1 and, for every pair, checking whether routing through k beats the current best, builds the true all-pairs answer in place — no extra storage, no per-source restart. The badge on each vertex below is the current shortest distance in the row being narrated; the highlighted arrows show a two-hop improvement actually just found. Animated on: 4 vertices, directed weighted edges 0->1(5), 0->3(10), 1->2(3), 2->3(1) — find the shortest distance between every pair of vertices..
All-pairs shortest paths: give every vertex a turn as the waypoint
Row 0 initialized directly from its edges
Before any vertex is allowed as a waypoint, dist[i][j] is just the direct edge weight, 0 on the diagonal, or infinity where no edge exists. Row 0 starts at [0, 5, inf, 10] — only the two edges leaving vertex 0 are known yet.
1FUNCTION floydWarshall(n, edges):2 FOR i FROM 0 TO n - 13 FOR j FROM 0 TO n - 14 dist[i][j] <- INFINITY5 dist[i][i] <- 06 FOR EACH (a, b, w) IN edges7 dist[a][b] <- w8 FOR k FROM 0 TO n - 19 FOR i FROM 0 TO n - 110 FOR j FROM 0 TO n - 111 IF dist[i][k] + dist[k][j] < dist[i][j]12 dist[i][j] <- dist[i][k] + dist[k][j]13 RETURN dist
← / → step · space play · Home restart