⚙️AlgorithmIntermediate

Floyd-Warshall Algorithm

Key Points

  • •
    Floyd–Warshall computes the shortest distances between all pairs of vertices in O() time using dynamic programming.
  • •
    It iteratively improves paths by allowing intermediate vertices up to k, using the recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
  • •
    The algorithm works with negative edge weights and detects negative cycles by checking if dist[i][i] < 0 for any i.
  • •
    You only need one n×n matrix for in-place updates, giving O() space, and this is safe because k increases monotonically.
  • •
    It generalizes to other problems like transitive closure (Warshall’s algorithm over the Boolean semiring).
  • •
    You can reconstruct actual shortest paths with a next matrix that remembers the next hop on each shortest path.
  • •
    For contest problems, use long long with a large INF and guard against overflow when adding distances.
  • •
    You can also count the number of shortest paths by tracking counts alongside distances and combining counts when equal minima occur.

Prerequisites

  • →Graphs and representations (adjacency matrix/list) — Floyd–Warshall operates on directed weighted graphs and is most naturally implemented with an adjacency matrix.
  • →Dynamic Programming fundamentals — The algorithm’s recurrence and in-place layering over k are core DP ideas.
  • →Single-source shortest paths (Dijkstra, Bellman–Ford) — Helps compare trade-offs and understand handling of negative edges and cycles.
  • →Asymptotic complexity (Big-O) — To judge when O(n^3) time and O(n^2) space are appropriate.
  • →Integer ranges and overflow handling — Prevent erroneous updates when adding large INF sentinels in 64-bit arithmetic.
  • →Boolean algebra and logic — For understanding Warshall’s transitive closure as OR/AND over paths.

Detailed Explanation

Tap terms for definitions

01Overview

Floyd–Warshall is a classic dynamic programming algorithm for the all-pairs shortest path (APSP) problem on a weighted directed graph. Instead of solving from one source at a time (like Dijkstra or Bellman–Ford), it improves distances for every pair (i, j) together, by gradually permitting more possible intermediate vertices. After k steps, the algorithm guarantees that the current distance from i to j is the shortest among paths whose internal vertices are drawn from {0, 1, ..., k−1}. The key insight is that any shortest path either avoids vertex k or uses it exactly once at some point, so you can always try to improve via i → k → j. With three nested loops over k, i, and j, every ordered triple is considered, yielding O(n^3) time.

Floyd–Warshall gracefully handles negative edge weights and can detect negative cycles: if the best distance from i to i becomes negative, there is a cycle of negative total weight reachable from i. Moreover, it generalizes to other closure problems; with Boolean operations instead of numeric min/+, you get Warshall’s algorithm for transitive closure (reachability). With careful bookkeeping, you can reconstruct actual paths and even count how many distinct shortest paths exist. The algorithm is simple to implement, space efficient (O(n^2)), and especially strong on dense graphs or when you need many source–target queries answered at once.

02Intuition & Analogies

Imagine a city map where you want to know the fastest route between every pair of neighborhoods. One approach is to pick one neighborhood as a hub and compute distances to all others, repeating for every starting neighborhood—this is like running Dijkstra or Bellman–Ford n times. Floyd–Warshall takes a different perspective: line up all neighborhoods in a list, and say, “First, consider routes that are not allowed to pass through any neighborhood as an intermediate stop; next, allow passing through the first one; then allow the first two; and so on.” Each time you expand the set of allowed stopovers, some trips may become faster because a newly-allowed neighborhood serves as a helpful transfer point.

Think of building itineraries with more authorized layovers. For a fixed transfer node k, ask: could going from i to k and then from k to j beat my current best i → j plan? If yes, update it. If not, keep the old one. Repeat for every i, j. By the time you’ve allowed all neighborhoods, you’ve considered every possible place to transfer, so your plan between i and j must be optimal.

This also explains how negative cycles show up: if there exists a loop that reduces your total travel time whenever you circle it, the best “time from a place back to itself” becomes negative—the sure sign that looping makes things arbitrarily better. Replace “time” with “can reach?” and swap min/+ with OR/AND and you get transitive closure: a path exists from i to j if either you already had one or you can go i → k and k → j. Same three-loop structure, different arithmetic.

03Formal Definition

Let G = (V, E) be a directed graph with = n and edge weights w: E → ℝ. Define [i][j] to be the length of the shortest path from i to j whose internal vertices are contained in the set {0, 1, ..., k−1}. The base case [i][j] is w(i, j) if (i, j) ∈ E, 0 if , and +∞ otherwise. The Floyd–Warshall recurrence is: [i][j] = min( [i][j], [i][k] + [k][j] ). After n iterations, [i][j] equals the shortest path distance from i to j, if it is finite. A negative cycle is detected if there exists a vertex v with [v][v] < 0. This can be seen as dynamic programming over subsets of allowed intermediates indexed by k, and equivalently as computing closure under the min-plus semiring (S, ⊕, ⊗) where S = ℝ ∪ {+∞}, a ⊕ , b), and a ⊗ . In this algebra, the recurrence is ⊕ (D[:, k] ⊗ D[k, :]). In the Boolean semiring (S = {false, true}, ⊕ = OR, ⊗ = AND), the same structure yields Warshall’s transitive closure.

04When to Use

Use Floyd–Warshall when you need distances between many or all pairs of vertices and the graph is small-to-medium (e.g., n up to a few hundred) or fairly dense. It shines in problems where multiple queries of shortest paths are required after a one-time preprocessing step, because the O(n^3) preprocessing gives O(1) query time thereafter. It is also the go-to method when negative edge weights are present (but no negative cycles) and you need all-pairs results without the complexity of Johnson’s algorithm.

Choose it for tasks like: computing minimal travel times between all cities; evaluating best exchange rates across many currencies (detecting arbitrage as a negative cycle); finding reachability/transitive closure in prerequisite graphs; or as a subroutine in dynamic programming on graphs where min-plus closure is natural. In contests, it’s a solid pick for n ≤ 400–600 depending on time limits and constant factors, or whenever input is given as an adjacency matrix.

If the graph is very sparse and large, prefer Johnson’s algorithm (reweights + Dijkstra) or run Dijkstra from all sources with a good priority queue. For only a few sources, simply run single-source algorithms from those sources.

⚠️Common Mistakes

• Overflow with INF: Using a too-large INF and then adding dist[i][k] + dist[k][j] can overflow long long. Always guard by checking reachability first (dist[i][k] == INF or dist[k][j] == INF) before addition, or use INF = 4e18 and avoid adding when either term is INF.

• Not initializing the diagonal: Forgetting dist[i][i] = 0 breaks correctness and negative-cycle detection.

• Mishandling multiple edges: When reading edges, keep the minimum weight among parallel edges; otherwise, you may overestimate distances or miscount shortest paths.

• Wrong loop order or in-place doubts: The correct order is for k in 0..n-1, then i, then j. In-place updates are safe only with this order because you never use a value that still allows intermediates beyond k.

• Ignoring negative cycles: Simply reading dist after the algorithm without checking dist[i][i] < 0 can yield misleading finite numbers for pairs affected by negative cycles. Properly propagate −∞ to all pairs (i, j) that can reach and exit a negatively-cycling vertex.

• Path reconstruction bugs: For the next-matrix approach, set next[i][j] = j on direct edges and update next[i][j] = next[i][k] upon relaxation. Don’t try to reconstruct paths when i→j is unreachable or when a negative cycle affects the pair.

• Modulo and counting pitfalls: When counting shortest paths, ensure you reset counts on strictly better distances and only sum counts when new distance equals the existing optimum. Watch for negative cycles or zero-weight cycles which can lead to infinite counts.

Key Formulas

Base Initialization

Explanation: Start with zero distance to self, edge weights for direct edges, and infinity for non-edges. This sets up the DP table for improvements.

Floyd–Warshall Recurrence

Explanation: Allowing vertex k as an intermediate can only improve if going through k is better than the current best. Repeat for all k to account for every possible intermediate.

Asymptotic Complexity

Explanation: Three nested loops over n vertices give cubic time, and the n×n distance matrix uses quadratic space.

Negative Cycle Test

Explanation: If the best distance from a node to itself is negative after completion, there is a cycle of negative total weight, implying unboundedly decreasing path costs.

Semiring View

Explanation: The update can be expressed with min as addition and + as multiplication, highlighting that the algorithm is a closure computation in the min-plus semiring.

Warshall (Transitive Closure)

Explanation: Replace arithmetic with logical operations to compute reachability: a path exists if it already did or if i can reach k and k can reach j.

Counting Shortest Paths

Explanation: Maintain counts C alongside distances D. When a strictly better route via k is found, reset the count to the product of subcounts; when an equal route is found, add the product.

Complexity Analysis

Floyd–Warshall performs three nested loops over the vertex set: for each k in 0..n−1, for each i, and for each j, it tries to improve dist[i][j] via k. Each innermost operation is O(1), aside from constant-time checks and additions, which yields a total running time of O(). In practice, the constant factors are small, and the algorithm is very simple, but cubic time means it is best suited for n up to a few hundred in typical contest environments. Space complexity is O(), since the algorithm stores a distance matrix and optionally a next (or predecessor) matrix of the same size for path reconstruction, plus minor overhead. An important optimization is that you do not need to keep separate layers and ; in-place updates are correct because the recurrence at step k only reads values that already account for intermediates from {0..k−1}. Thus, a single matrix suffices. Comparatively, running Dijkstra from all sources is roughly O(n·(m log n)) for sparse graphs with nonnegative edges, which often beats O() when m ≪ . Johnson’s algorithm computes APSP in O(n·m log n) even with negative edges (but no negative cycles). Conversely, Floyd–Warshall is competitive and typically preferable on dense graphs (m ≈ ), for small to medium n, or when the input is an adjacency matrix and you need additional features like transitive closure or easy path reconstruction. Caveats for performance: ensure INF guards to avoid overflow; avoid unnecessary branching in the inner loop; consider using 32-bit ints for indices and 64-bit longs for weights; and note that negative-cycle propagation (marking −∞ pairs) adds an extra O() pass but is still cubic overall.

Code Examples

Basic Floyd–Warshall with Path Reconstruction
1#include <bits/stdc++.h>
2using namespace std;
3
4static const long long INF = (long long)4e18; // safe INF for long long
5
6// Reconstruct shortest path from s to t using next-hop matrix.
7vector<int> reconstruct_path(int s, int t, const vector<vector<int>>& nxt) {
8    if (s == t) return {s};
9    if (nxt[s][t] == -1) return {}; // unreachable
10    vector<int> path = {s};
11    int u = s;
12    while (u != t) {
13        u = nxt[u][t];
14        if (u == -1) { // defensive: should not happen if reachable
15            path.clear();
16            return path;
17        }
18        path.push_back(u);
19        if ((int)path.size() > 1000000) break; // guard in pathological cases
20    }
21    return path;
22}
23
24int main() {
25    ios::sync_with_stdio(false);
26    cin.tie(nullptr);
27
28    int n, m;
29    // Example input format:
30    // n m
31    // m lines: u v w (0-indexed)
32    if (!(cin >> n >> m)) {
33        // Fallback demo graph if no input provided
34        n = 4; m = 5;
35        vector<tuple<int,int,long long>> edges = {
36            {0,1,5}, {0,3,10}, {1,2,3}, {2,3,1}, {0,2,100}
37        };
38        vector<vector<long long>> dist(n, vector<long long>(n, INF));
39        vector<vector<int>> nxt(n, vector<int>(n, -1));
40        for (int i = 0; i < n; ++i) dist[i][i] = 0;
41        for (auto [u,v,w] : edges) {
42            if (w < dist[u][v]) {
43                dist[u][v] = w;
44                nxt[u][v] = v;
45            }
46        }
47        for (int k = 0; k < n; ++k)
48            for (int i = 0; i < n; ++i)
49                if (dist[i][k] != INF)
50                    for (int j = 0; j < n; ++j) {
51                        if (dist[k][j] == INF) continue;
52                        long long cand = dist[i][k] + dist[k][j];
53                        if (cand < dist[i][j]) {
54                            dist[i][j] = cand;
55                            nxt[i][j] = nxt[i][k];
56                        }
57                    }
58        // Print distances
59        cout << "Distance matrix:\n";
60        for (int i = 0; i < n; ++i) {
61            for (int j = 0; j < n; ++j) {
62                if (dist[i][j] >= INF/2) cout << "INF "; else cout << dist[i][j] << ' ';
63            }
64            cout << '\n';
65        }
66        // Reconstruct a sample path 0 -> 3
67        auto path = reconstruct_path(0, 3, nxt);
68        cout << "Path 0->3: ";
69        if (path.empty()) cout << "unreachable\n";
70        else {
71            for (int i = 0; i < (int)path.size(); ++i) {
72                if (i) cout << " -> ";
73                cout << path[i];
74            }
75            cout << '\n';
76        }
77        return 0;
78    }
79
80    vector<vector<long long>> dist(n, vector<long long>(n, INF));
81    vector<vector<int>> nxt(n, vector<int>(n, -1));
82    for (int i = 0; i < n; ++i) dist[i][i] = 0;
83
84    for (int e = 0; e < m; ++e) {
85        int u, v; long long w; cin >> u >> v >> w;
86        if (w < dist[u][v]) { // keep the minimum among parallel edges
87            dist[u][v] = w;
88            nxt[u][v] = v;
89        }
90    }
91
92    for (int k = 0; k < n; ++k)
93        for (int i = 0; i < n; ++i)
94            if (dist[i][k] != INF)
95                for (int j = 0; j < n; ++j) {
96                    if (dist[k][j] == INF) continue;
97                    long long cand = dist[i][k] + dist[k][j];
98                    if (cand < dist[i][j]) {
99                        dist[i][j] = cand;
100                        nxt[i][j] = nxt[i][k];
101                    }
102                }
103
104    // Output distances
105    for (int i = 0; i < n; ++i) {
106        for (int j = 0; j < n; ++j) {
107            if (dist[i][j] >= INF/2) cout << "INF";
108            else cout << dist[i][j];
109            cout << (j+1==n?'\n':' ');
110        }
111    }
112
113    // Example query: reconstruct path from 0 to n-1 if desired
114    // vector<int> p = reconstruct_path(0, n-1, nxt);
115    return 0;
116}
117

This implementation initializes the distance matrix with 0 on the diagonal, direct edge weights elsewhere, and INF when no edge exists. It updates distances in-place while k grows, safely using the next matrix to reconstruct actual shortest paths by walking from s to t via recorded next hops.

Time: O(n^3)Space: O(n^2)
Negative Cycle Detection and −∞ Propagation
1#include <bits/stdc++.h>
2using namespace std;
3
4static const long long INF = (long long)4e18;
5
6int main() {
7    ios::sync_with_stdio(false);
8    cin.tie(nullptr);
9
10    int n, m; cin >> n >> m;
11    vector<vector<long long>> dist(n, vector<long long>(n, INF));
12    for (int i = 0; i < n; ++i) dist[i][i] = 0;
13
14    for (int e = 0; e < m; ++e) {
15        int u, v; long long w; cin >> u >> v >> w;
16        dist[u][v] = min(dist[u][v], w);
17    }
18
19    for (int k = 0; k < n; ++k)
20        for (int i = 0; i < n; ++i)
21            if (dist[i][k] != INF)
22                for (int j = 0; j < n; ++j) {
23                    if (dist[k][j] == INF) continue;
24                    long long cand = dist[i][k] + dist[k][j];
25                    if (cand < dist[i][j]) dist[i][j] = cand;
26                }
27
28    // Mark pairs affected by any negative cycle with -INF
29    vector<vector<bool>> neg(n, vector<bool>(n, false));
30    for (int v = 0; v < n; ++v) if (dist[v][v] < 0) {
31        for (int i = 0; i < n; ++i) if (dist[i][v] != INF)
32            for (int j = 0; j < n; ++j) if (dist[v][j] != INF)
33                neg[i][j] = true; // any path i->...->v->...->j can be made arbitrarily small
34    }
35
36    // Print result matrix with INF and -INF annotations
37    for (int i = 0; i < n; ++i) {
38        for (int j = 0; j < n; ++j) {
39            if (neg[i][j]) cout << "-INF";
40            else if (dist[i][j] >= INF/2) cout << "INF";
41            else cout << dist[i][j];
42            cout << (j+1==n?'\n':' ');
43        }
44    }
45    return 0;
46}
47

After running Floyd–Warshall, a negative cycle is detected if dist[v][v] < 0. Any pair (i, j) that can reach v and be reached from v is affected, because you can loop around the negative cycle to reduce the path cost without bound. The code marks such pairs as −INF and prints them accordingly.

Time: O(n^3)Space: O(n^2)
Warshall’s Algorithm for Transitive Closure (Reachability)
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    ios::sync_with_stdio(false);
6    cin.tie(nullptr);
7
8    int n, m; cin >> n >> m;
9    vector<vector<unsigned char>> reach(n, vector<unsigned char>(n, 0));
10    for (int i = 0; i < n; ++i) reach[i][i] = 1; // each node reaches itself
11
12    for (int e = 0; e < m; ++e) {
13        int u, v; cin >> u >> v;
14        reach[u][v] = 1;
15    }
16
17    for (int k = 0; k < n; ++k)
18        for (int i = 0; i < n; ++i)
19            if (reach[i][k])
20                for (int j = 0; j < n; ++j)
21                    reach[i][j] = (reach[i][j] || (reach[i][k] && reach[k][j]));
22
23    // Print reachability matrix (1 if reachable, 0 otherwise)
24    for (int i = 0; i < n; ++i) {
25        for (int j = 0; j < n; ++j) {
26            cout << (reach[i][j] ? 1 : 0) << (j+1==n?'\n':' ');
27        }
28    }
29    return 0;
30}
31

This is the Boolean variant of Floyd–Warshall. It replaces arithmetic with logical OR/AND and computes whether j is reachable from i via any sequence of intermediates. It is useful for dependency graphs, prerequisite checks, and computing closure of relations.

Time: O(n^3)Space: O(n^2)
Counting the Number of Shortest Paths (Modulo 1e9+7)
1#include <bits/stdc++.h>
2using namespace std;
3
4static const long long INF = (long long)4e18;
5static const long long MOD = 1000000007LL;
6
7int main() {
8    ios::sync_with_stdio(false);
9    cin.tie(nullptr);
10
11    int n, m; cin >> n >> m;
12    vector<vector<long long>> dist(n, vector<long long>(n, INF));
13    vector<vector<long long>> cnt(n, vector<long long>(n, 0));
14
15    for (int i = 0; i < n; ++i) {
16        dist[i][i] = 0;
17        cnt[i][i] = 1; // one empty path from i to i (helps composition)
18    }
19
20    for (int e = 0; e < m; ++e) {
21        int u, v; long long w; cin >> u >> v >> w;
22        if (w < dist[u][v]) {
23            dist[u][v] = w;
24            cnt[u][v] = 1; // best direct edge so far
25        } else if (w == dist[u][v]) {
26            cnt[u][v] = (cnt[u][v] + 1) % MOD; // another edge with same minimal weight
27        }
28    }
29
30    for (int k = 0; k < n; ++k)
31        for (int i = 0; i < n; ++i) if (dist[i][k] != INF)
32            for (int j = 0; j < n; ++j) {
33                if (dist[k][j] == INF) continue;
34                long long cand = dist[i][k] + dist[k][j];
35                if (cand < dist[i][j]) {
36                    dist[i][j] = cand;
37                    cnt[i][j] = (cnt[i][k] * cnt[k][j]) % MOD; // reset with new best
38                } else if (cand == dist[i][j]) {
39                    cnt[i][j] = (cnt[i][j] + (cnt[i][k] * cnt[k][j]) % MOD) % MOD; // add equal-best decompositions
40                }
41            }
42
43    // NOTE: This assumes no negative cycles affect any pair; otherwise counts may be infinite.
44
45    // Output: for each pair print distance and number of shortest paths
46    for (int i = 0; i < n; ++i) {
47        for (int j = 0; j < n; ++j) {
48            if (dist[i][j] >= INF/2) {
49                cout << "INF:0"; // no path
50            } else {
51                // For i==j, distance 0 and cnt>=1 include the empty path.
52                cout << dist[i][j] << ':' << (cnt[i][j] % MOD);
53            }
54            cout << (j+1==n?'\n':' ');
55        }
56    }
57
58    return 0;
59}
60

The code maintains both distances and counts. When a strictly better path via k is found, it replaces the count with the product of subcounts (number of ways to reach k times number of ways from k to j). When an equal path is found, it adds the product. This follows the same DP layering by k and avoids double counting. We print distances and the number of shortest paths modulo 1e9+7.

Time: O(n^3)Space: O(n^2)