Algorithms/Graph/Floyd-Warshall

Floyd-Warshall

All-pairs shortest paths via dynamic programming — handles negative weights and detects negative cycles.

GraphAll-PairsDynamic ProgrammingNegative WeightsO(V³)

All-Pairs Distance Matrix

Intermediate—

1 / 0

Speed

⚖️ All-Pairs vs. Single-Source

Floyd-Warshall runs once and computes shortest paths between every pair of vertices in O(V³). Running Dijkstra from each source would be O(V · (V+E) log V) and cannot handle negative edges. Running Bellman-Ford from each source would be O(V² · E). Compare Bellman-Ford →

floydWarshall.js

1function floydWarshall(nodes, edges) {

2 const V = nodes.length;

3 // Initialize dist[][] and next[][]

4 for (let i = 0; i < V; i++) {

5 for (let j = 0; j < V; j++) {

6 dist[i][j] = (i === j) ? 0 : Infinity;

7 next[i][j] = (i === j) ? nodes[i] : null;

8 }

9 }

10 for (const [u, v, w] of edges) {

11 dist[u][v] = w; // direct edge weight

12 next[u][v] = v; // next hop is v itself

13 }

15 // Triple-nested relaxation

16 for (let k = 0; k < V; k++) {

17 for (let i = 0; i < V; i++) {

18 for (let j = 0; j < V; j++) {

19 const via = dist[i][k] + dist[k][j];

20 if (via < dist[i][j]) {

21 dist[i][j] = via;

22 next[i][j] = next[i][k];

23 }

24 }

25 }

26 }

28 // Check for negative cycles (dist[i][i] < 0)

29 for (let i = 0; i < V; i++) {

30 if (dist[i][i] < 0) return { hasNegativeCycle: true };

31 }

33 return { dist, next };

34}

Algorithm Explanation

Floyd-Warshall is a dynamic programming algorithm that computes the shortest paths between all pairs of vertices in a weighted graph in a single run — handling negative edge weights (but not negative cycles).

⚙️ How It Works

Initialize — Build a V×V matrix where dist[i][i] = 0, direct edges get their weight, and all others are ∞.
Relax via every vertex k — For each intermediate vertex k (in turn), check every pair (i, j): if going through k is cheaper, update dist[i][j].
Path reconstruction — Maintain a next[i][j] matrix pointing to the next hop so any path can be traced in O(V).
Detect negative cycles — After the loop, if any dist[i][i] < 0, a negative cycle exists.

🔑 Why DP Works Here

Define dist[k][i][j] as the shortest path from i to j using only vertices 0…k as intermediates. The recurrence is:

dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])

Since k can only shrink distances, the current matrix in-place update is safe — you never read a cell before it has been correctly set for the current k.

⚠️ Negative cycles: If any vertex ends up with dist[v][v] < 0 after the main loop, the graph contains a negative cycle and all shortest-path values involving that vertex are undefined.

⚖️ Floyd-Warshall vs. Single-Source Algorithms

Problem solved

Floyd-Warshall solves all-pairs. Dijkstra / Bellman-Ford solve single-source and must be run V times for all-pairs.

Negative weights

Floyd-Warshall and Bellman-Ford handle them. Dijkstra requires non-negative weights. Compare Bellman-Ford →

Dense vs. sparse

Floyd-Warshall is O(V³) — best when the graph is dense or you need all pairs. On sparse graphs, repeated Dijkstra is faster: O(V · E · log V).

Step through the O(V³) relaxation loop · Watch the matrix update in real time · Reconstruct any path instantly