Log inSign up
mediumGeeksforGeeksNot Started

Floyd Warshall Algorithm

Given a weighted directed graph represented as an adjacency matrix of size V x V where matrix[i][j] is the weight of directed edge from i to j (or -1 if no edge). Find the shortest distances between all pairs of vertices in-place.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a directed graph represented as an adjacency matrix of size V x V, where matrix[i][j] represents the weight of the directed edge from vertex i to vertex j. If there is no edge from i to j, matrix[i][j] = -1.

Compute the shortest distances between every pair of vertices in-place. If vertex j is unreachable from vertex i, set matrix[i][j] = -1.

Furthermore, detect if a negative weight cycle exists anywhere in the graph. (If matrix[i][i] < 0 for any i, a negative cycle exists).

---

### Examples

Example 1: ``text Input: matrix = [ [0, 2, -1, -1], [1, 0, 3, -1], [-1, -1, 0, -1], [3, 5, 4, 0] ] Output: [ [0, 2, 5, -1], [1, 0, 3, -1], [-1, -1, 0, -1], [3, 5, 4, 0] ] Explanation: - Distance 0 -> 2: 0 -> 1 -> 2 (2 + 3 = 5). - Other entries already optimal or unreachable.

Example 2 (Negative Cycle Detection): ``text If after all iterations dist[i][i] < 0 for any i, a negative weight cycle exists.

---

### Constraints - 1 <= V <= 500 - -1000 <= matrix[i][j] <= 1000 - matrix[i][i] = 0

Constraints:

  • 1 <= V <= 500
  • -1000 <= matrix[i][j] <= 1000
  • 0-indexed V x V matrix

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate the dynamic programming subproblem over allowed intermediate vertices.
  • Understand why the intermediate loop k must be outermost.
  • Detect negative weight cycles by inspecting self-distances matrix[i][i] < 0.
  • Implement in-place matrix updates across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • All-pairs shortest paths on small/medium graphs (V <= 500).
  • Finding graph diameter, center, or transitive closure (Warshall's algorithm).
  • Detecting any negative cycle in the entire graph.

Algorithmic Decision Tree:

  • If single-source shortest path with positive weights -> Dijkstra O((V + E) log V).
  • If single-source with negative weights -> Bellman-Ford O(V * E).
  • If all-pairs shortest paths -> Floyd-Warshall O(V3).

Connected Patterns:

Bellman Ford AlgorithmDijkstra Shortest PathTransitive Closure

1. Repeated Bellman-Ford from Every Vertex

Intuition

Execute Bellman-Ford V times, treating each vertex i as the source to construct the V x V distance matrix.

Algorithm

  1. Convert adjacency matrix into an edge list.
  2. For each vertex i from 0 to V - 1:
  3. Run Bellman-Ford with source = i.
  4. Copy resulting distance array into row i of output matrix.
  5. Return the V x V matrix.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6const int INF = 1e8;
7
8void floydWarshallBellmanFord(vector<vector<int>>& matrix) {
9 int V = matrix.size();
10 vector<vector<int>> edges;
11
12 for (int i = 0; i < V; ++i) {
13 for (int j = 0; j < V; ++j) {
14 if (i != j && matrix[i][j] != -1) {
15 edges.push_back({i, j, matrix[i][j]});
16 }
17 }
18 }
19
20 for (int src = 0; src < V; ++src) {
21 vector<int> dist(V, INF);
22 dist[src] = 0;
23
24 for (int i = 0; i < V - 1; ++i) {
25 for (const auto& e : edges) {
26 int u = e[0], v = e[1], w = e[2];
27 if (dist[u] != INF && dist[u] + w < dist[v]) {
28 dist[v] = dist[u] + w;
29 }
30 }
31 }
32
33 for (int j = 0; j < V; ++j) {
34 matrix[src][j] = (dist[j] >= INF) ? -1 : dist[j];
35 }
36 }
37}
38
39int main() {
40 vector<vector<int>> matrix = {
41 {0, 2, -1, -1},
42 {1, 0, 3, -1},
43 {-1, -1, 0, -1},
44 {3, 5, 4, 0}
45 };
46
47 floydWarshallBellmanFord(matrix);
48 cout << "Shortest Matrix via Repeated Bellman-Ford:" << endl;
49 for (const auto& row : matrix) {
50 for (int d : row) cout << d << " ";
51 cout << endl;
52 }
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(V^2 * E) ≈ O(V^4) in dense graphs
  • Space complexity: O(V^2)

2. Matrix Multiplication All-Pairs DP

Intuition

Formulate shortest paths as (min, +) matrix exponentiation, computing all paths of length <= 2k in log V matrix multiplication rounds.

Algorithm

  1. Define matrix multiplication where multiplication is replaced by addition and addition by minimum.
  2. Compute L^(2) = L * L, L^(4) = L^(2) * L^(2) up to L^(V-1) using binary exponentiation.
  3. Total rounds = log V, each taking O(V3).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7const int INF = 1e8;
8
9vector<vector<int>> multiply(const vector<vector<int>>& A, const vector<vector<int>>& B) {
10 int n = A.size();
11 vector<vector<int>> C(n, vector<int>(n, INF));
12 for (int i = 0; i < n; ++i) {
13 for (int j = 0; j < n; ++j) {
14 for (int k = 0; k < n; ++k) {
15 if (A[i][k] != INF && B[k][j] != INF) {
16 C[i][j] = min(C[i][j], A[i][k] + B[k][j]);
17 }
18 }
19 }
20 }
21 return C;
22}
23
24int main() {
25 int V = 4;
26 vector<vector<int>> A = {
27 {0, 2, INF, INF},
28 {1, 0, 3, INF},
29 {INF, INF, 0, INF},
30 {3, 5, 4, 0}
31 };
32
33 auto res = A;
34 for (int m = 1; m < V - 1; m *= 2) {
35 res = multiply(res, res);
36 }
37
38 cout << "Matrix Multiplication Result (0, 2): " << res[0][2] << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(V^3 log V)
  • Space complexity: O(V^2)

3. Floyd-Warshall 3-Nested Loop In-Place Dynamic Programming

Intuition

Execute the classic O(V3) algorithm in-place. Loop k from 0 to V - 1, then for each (i, j), relax matrix[i][j] using intermediate vertex k.

Algorithm

  1. Replace all -1 with a sentinel INF = 1e8 (except diagonal matrix[i][i] = 0).
  2. Outer loop k from 0 to V - 1 (intermediate candidate vertex):
  3. Loop i from 0 to V - 1 (source vertex):
  4. Loop j from 0 to V - 1 (destination vertex):
  5. If matrix[i][k] != INF and matrix[k][j] != INF:
  6. matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]).
  7. Negative cycle check: If matrix[i][i] < 0 for any i, flag negative cycle.
  8. Restore unreachable entries: for every (i, j), if matrix[i][j] >= INF, set matrix[i][j] = -1.
  9. Return modified matrix.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7const int INF = 1e8;
8
9void floydWarshall(vector<vector<int>>& matrix) {
10 int V = matrix.size();
11
12 // 1. Replace -1 with INF (except diagonal)
13 for (int i = 0; i < V; ++i) {
14 for (int j = 0; j < V; ++j) {
15 if (matrix[i][j] == -1) matrix[i][j] = INF;
16 }
17 }
18
19 // 2. Floyd-Warshall DP: k must be outermost!
20 for (int k = 0; k < V; ++k) {
21 for (int i = 0; i < V; ++i) {
22 for (int j = 0; j < V; ++j) {
23 if (matrix[i][k] != INF && matrix[k][j] != INF) {
24 matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
25 }
26 }
27 }
28 }
29
30 // 3. Optional: Negative cycle check
31 for (int i = 0; i < V; ++i) {
32 if (matrix[i][i] < 0) {
33 cout << "Negative cycle detected through vertex " << i << endl;
34 }
35 }
36
37 // 4. Restore INF to -1
38 for (int i = 0; i < V; ++i) {
39 for (int j = 0; j < V; ++j) {
40 if (matrix[i][j] >= INF) matrix[i][j] = -1;
41 }
42 }
43}
44
45int main() {
46 vector<vector<int>> matrix = {
47 {0, 2, -1, -1},
48 {1, 0, 3, -1},
49 {-1, -1, 0, -1},
50 {3, 5, 4, 0}
51 };
52
53 floydWarshall(matrix);
54 cout << "Optimal Floyd-Warshall Result:" << endl;
55 for (const auto& row : matrix) {
56 for (int d : row) cout << d << " ";
57 cout << endl;
58 }
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(V^3)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Repeated Bellman-Ford from Every VertexO(V^2 * E) ≈ O(V^4) on dense graphsO(V^2)Run Bellman-Ford V times, once for each vertex as source.Iterating V * (V - 1) * E times.
2.Repeated Dijkstra from Every Vertex (Johnson's Algorithm)O(V * (V + E) log V)O(V + E)Reweight edges using Bellman-Ford potentials, then run Dijkstra V times.Reweighting overhead.
3.Floyd-Warshall 3-Nested Loop DP (Optimal)OptimalO(V^3)O(1) auxiliaryOuter loop k treats each node as an intermediate stop. Update matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]).Triple nested loop.

Common Pitfalls & Crucial Edge Cases

Placing loop k inside i and j

The most infamous mistake; breaks DP correctness.

Integer overflow with INF

Adding matrix[i][k] + matrix[k][j] when one is 1e9 can cause integer overflow in 32-bit signed integers; use a safe sentinel like 1e8.

Forgetting to restore -1

If the problem specifies -1 for unreachable nodes, restore sentinels back to -1 before returning.

Crucial Edge Cases to Validate:

  • Unreachable pairs — Handled using a large sentinel (1e8) to avoid arithmetic overflow when adding infinity.
  • Self-loops with negative weight — Immediately sets matrix[i][i] < 0.
  • Disconnected graph — Handled naturally; unreachable sub-matrices remain sentinel / -1.
  • Negative weights without cycles — Handled correctly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the DP state definition clearly: 'Shortest path from i to j using intermediate vertices from {0..k}'.
  2. Mention negative cycle detection via the main diagonal dist[i][i] < 0.
  3. Highlight the relationship with Warshall's transitive closure (replace min with OR, and + with AND).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the intermediate vertex loop k be the OUTERMOST loop in Floyd-Warshall?

2.How do you detect whether the graph contains a negative weight cycle after running Floyd-Warshall?

Back to DSA Sheet