Floyd-Warshall Algorithm

Quick Revisit

• USE WHEN: All-pairs shortest paths on small graphs ($n\le 400$), or negative edges without negative-cycle detection by Dijkstra
• INVARIANT: After processing intermediate node $k$, dist[i][j] is optimal over paths using only nodes $0..k$
• TIME: O(n³) | SPACE: O(n²)
• CLASSIC BUG: Putting the $k$ (intermediate node) loop inside instead of outermost — breaks the DP layering
• PRACTICE: 05-ladder-graphs

All-pairs shortest paths in $O(n^3)$ -- the brute-force DP that solves every pair at once, works with negative edges, and detects negative cycles.

Difficulty: [Intermediate]Prerequisites: Graph RepresentationCF Rating: 1500-1800 AL-17

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

The Pain

You have a small directed weighted graph with 4 vertices and you need the shortest path between every pair $(i,j)$.

The naive plan: run Dijkstra from each of the $n$ sources. That costs $n\times O(m\log n)$. For a dense graph where $m=O(n^2)$ this becomes $O(n^3\log n)$ -- and you pay the overhead of a priority queue $n$ times. Dijkstra also cannot handle negative edge weights at all.

There has to be a simpler, loop-only approach that solves everything in one pass over a matrix.

The Key Insight

Open hubs one by one. The outer loop $k$ is not a loop variable — it is a DP layer.

The whole algorithm is a layered DP over allowed intermediate sets. Define $d^{(k)}[i][j]$ = shortest path from $i$ to $j$ whose internal vertices all lie in $\{0,1,\dots ,k\}$. The recurrence is

$$d^{(k)}[i][j]=min(d^{(k-1)}[i][j],d^{(k-1)}[i][k]+d^{(k-1)}[k][j]).$$

Three nested loops compute layer $k$ from layer $k-1$. Putting $k$ on the outside is not a stylistic choice; it is the only order under which the layering argument is valid. If $k$ is inside, the right-hand side mixes a half-updated table with an unfinished one, and the algorithm silently returns wrong answers.

The simplest way to remember: each value of $k$ corresponds to opening one new hub airport globally; only after every $i\to j$ pair has been re-examined with this hub available do you move on to the next hub.

Analogy: an airline route network. Every time a new hub airport opens (that is node $k$), you check whether any origin-destination pair now has a cheaper connection through that hub. After all hubs have opened, every route is optimal.

Visual Walkthrough

Consider this 4-vertex directed weighted graph:

        2         6
   0 -------> 1 -------> 3
   |                      ^
   |  8                   | 1
   +--------> 2 ---------+

Edges: $(0\to 1,w=2)$, $(1\to 3,w=6)$, $(0\to 2,w=8)$, $(2\to 3,w=1)$.

Initial distance matrix (INF = no direct edge):

       0     1     2     3
  0 [  0     2     8   INF ]
  1 [INF     0   INF     6 ]
  2 [INF   INF     0     1 ]
  3 [INF   INF   INF     0 ]

Step k = 0 -- allow intermediate vertex {0}:

       0     1     2     3
  0 [  0     2     8   INF ]
  1 [INF     0   INF     6 ]   (no pair improves through 0)
  2 [INF   INF     0     1 ]
  3 [INF   INF   INF     0 ]

No changes. No vertex can reach another more cheaply via 0.

Step k = 1 -- allow intermediates {0, 1}:

       0     1     2     3
  0 [  0     2     8   * 8 ]   <-- dist[0][3] = dist[0][1] + dist[1][3]
  1 [INF     0   INF     6 ]                   = 2 + 6 = 8
  2 [INF   INF     0     1 ]
  3 [INF   INF   INF     0 ]

Routing $0\to 1\to 3$ costs 8, better than INF. Marked with *.

Step k = 2 -- allow intermediates {0, 1, 2}:

       0     1     2     3
  0 [  0     2     8   * 8 ]
  1 [INF     0   INF     6 ]   (no pair improves through 2;
  2 [INF   INF     0     1 ]    only row 0 reaches 2, and
  3 [INF   INF   INF     0 ]    dist[0][2]+dist[2][3] = 8+1 = 9 > 8)

No changes this round.

Step k = 3 -- allow intermediates {0, 1, 2, 3}:

       0     1     2     3
  0 [  0     2     8     8 ]
  1 [INF     0   INF     6 ]   (no improvement through 3 either)
  2 [INF   INF     0     1 ]
  3 [INF   INF   INF     0 ]

Final result: $\text{dist}[0][3]=8$ (path $0\to 1\to 3$), $\text{dist}[0][2]=8$ (direct), $\text{dist}[2][3]=1$ (direct).

The Invariant

Invariant. After processing intermediate nodes $\{0,1,\dots ,k\}$, $\text{dist}[i][j]$ equals the length of the shortest path from $i$ to $j$ whose internal vertices all belong to $\{0,1,\dots ,k\}$.

When $k=n-1$ the constraint vanishes -- every vertex is allowed as an intermediate -- so $\text{dist}[i][j]$ holds the true shortest-path distance.

The invariant also explains why $k$ must be the outermost loop: each layer $k$ builds on the completed results of layer $k-1$.

What the Code Won't Teach You

The loop order is not arbitrary -- it encodes a DP recurrence.

The three nested loops look interchangeable, but they are not. Conceptually, Floyd-Warshall computes a 3D DP table $d[k][i][j]$ = "shortest path from $i$ to $j$ using only intermediates from $\{0,\dots ,k\}$." The $k$ dimension is collapsed by updating in-place, which is safe because $d[i][k]$ and $d[k][j]$ are unaffected by the $k$-th round. If you swap the loop order and put $k$ inside, you mix different "generations" of the table -- using a $d[i][k]$ that was already updated for intermediates beyond $k$.

         d[k][i][j] = min( d[k-1][i][j],
                           d[k-1][i][k] + d[k-1][k][j] )
                              ^               ^
                              |               |
               "don't use k"    "route through k"

         In-place collapse: d[i][k] is the same in round k and k-1
         because adding k as intermediate can't improve a path TO k
         that already uses intermediates {0..k-1}.

Floyd-Warshall is not "Dijkstra for all pairs."

Dijkstra is greedy and single-source. Floyd-Warshall is DP and all-pairs. Dijkstra fails on negative edges; Floyd-Warshall handles them. Conceptually, Floyd-Warshall is closer to Bellman-Ford (relax everything, layer by layer) than to Dijkstra (greedily expand a frontier). The connection to Dijkstra is only that both solve shortest-path problems.

The decision of when NOT to use it matters more than knowing the algorithm.

  +----------------------------+-----------------------------------+
  | Scenario                   | Use                               |
  +----------------------------+-----------------------------------+
  | n <= 400-500, all-pairs    | Floyd-Warshall                    |
  | n > 500, sparse graph      | Dijkstra from each source         |
  | Only single-source needed  | Dijkstra or Bellman-Ford          |
  | Unweighted graph           | BFS from each source              |
  +----------------------------+-----------------------------------+

When to Reach for This

Trigger phrases in the problem statement:

• "all-pairs shortest path"
• small $n\le 500$ (the $O(n^3)$ budget)
• "transitive closure" or "reachability between all pairs"
• "negative edge weights" with all pairs needed

Counter-examples -- do NOT use Floyd-Warshall when:

• Graph is large and sparse ($n>500$, $m\ll n^2$). Run Dijkstra from every source: $O(n\cdot m\log n)$ is cheaper.
• Only single-source shortest paths are needed. Use Dijkstra (non-negative weights) or Bellman-Ford (negative weights).
• Graph is unweighted. BFS from every source runs in $O(n(n+m))$.

Choose this when

Floyd-Warshall is the right answer not just when the graph is dense. The decision usually comes down to a few combined signals:

• Small $n$ (roughly $n\le 400$–$500$, the $O(n^3)$ budget). This is the dominant constraint.
• Many queries about pairwise distances — running $n$ Dijkstras to answer all of them already costs about $O(n^2\log n+nm\log n)$, while one Floyd-Warshall does it in flat $O(n^3)$.
• Negative edge weights with no relevant negative cycles. Dijkstra fails; Bellman-Ford from each source is $O(n\cdot nm)=O(n^{2}m)$, which beats Floyd-Warshall only when $m\ll n$.
• Simple implementation matters — three nested loops, no priority queue, no edge list manipulation.

The "graph is dense" framing is partially misleading: Floyd-Warshall is often selected for small $n$ with many queries, even on sparse graphs, simply because running many single-source algorithms or maintaining a distance oracle costs more developer time and constant factor than three nested loops.

---

C++ STL Reference

Feature	Usage	Note
vector<vector<long long>>	2D distance matrix	Use long long to avoid overflow
numeric_limits<long long>::max() / 2	INF sentinel	Halved to prevent overflow on addition
min(a, b)	Relaxation	Core of the inner loop
bitset<N>	Transitive closure	$O(n^3/64)$ with bitwise OR
array<array<int,N>,N>	Fixed-size matrix	Faster than nested vectors for small $n$

---

Implementation (Contest-Ready)

Version 1 -- Minimal template (copy-paste for contest)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    const long long INF = 1e18;
    vector dist(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;
        u--; v--;
        dist[u][v] = min(dist[u][v], w); // handle multi-edges
    }

    // k MUST be the outermost loop
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    // negative cycle detection: dist[v][v] < 0 for some v
    for (int i = 0; i < n; i++)
        if (dist[i][i] < 0) {
            cout << "NEGATIVE CYCLE\n";
            return 0;
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (j) cout << ' ';
            cout << (dist[i][j] >= INF ? -1 : dist[i][j]);
            if (j == n - 1) cout << '\n';
        }
}

Version 2 -- With path reconstruction and explanations

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    const long long INF = 1e18;
    vector dist(n, vector<long long>(n, INF));
    // nxt[i][j] = next vertex on shortest path from i to j
    vector nxt(n, vector<int>(n, -1));

    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
        nxt[i][i] = i;
    }

    for (int i = 0; i < m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;
        u--; v--;
        if (w < dist[u][v]) {    // keep shortest among parallel edges
            dist[u][v] = w;
            nxt[u][v] = v;      // direct edge: next hop is destination
        }
    }

    // --- Core Floyd-Warshall ---
    // k = intermediate vertex under consideration
    // Invariant: after iteration k, dist[i][j] is the shortest path
    // using only vertices {0..k} as intermediates.
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] >= INF) continue; // prune: no path i->k
            for (int j = 0; j < n; j++) {
                if (dist[k][j] >= INF) continue; // prune: no path k->j
                long long candidate = dist[i][k] + dist[k][j];
                if (candidate < dist[i][j]) {
                    dist[i][j] = candidate;
                    nxt[i][j] = nxt[i][k]; // path goes through k
                }
            }
        }
    }

    // --- Negative cycle check ---
    bool has_neg_cycle = false;
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            has_neg_cycle = true;
            break;
        }
    }

    if (has_neg_cycle) {
        cout << "NEGATIVE CYCLE\n";
        return 0;
    }

    // --- Path reconstruction ---
    // Recover the actual shortest path from src to dst.
    auto get_path = [&](int src, int dst) -> vector<int> {
        if (nxt[src][dst] == -1) return {}; // no path
        vector<int> path = {src};
        while (src != dst) {
            src = nxt[src][dst];
            path.push_back(src);
        }
        return path;
    };

    // Example: print shortest path from 0 to n-1
    if (n >= 2) {
        auto path = get_path(0, n - 1);
        if (path.empty()) {
            cout << "NO PATH\n";
        } else {
            cout << "Distance: " << dist[0][n - 1] << '\n';
            cout << "Path:";
            for (int v : path) cout << ' ' << v + 1; // 1-indexed output
            cout << '\n';
        }
    }
}

Bonus -- Transitive closure with bitset ($O(n^3/64)$)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500;
bitset<MAXN> reach[MAXN];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) reach[i][i] = 1;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        reach[u][v] = 1;
    }

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            if (reach[i][k])
                reach[i] |= reach[k]; // bitwise OR: 64x speedup

    // reach[i][j] == 1 iff j is reachable from i
}

---

Operations Reference

Operation	Time	Space	Notes
Build distance matrix	$O(n^2)$	$O(n^2)$	Initialize + read edges
Floyd-Warshall (all pairs)	$O(n^3)$	$O(n^2)$	In-place on dist matrix
Path reconstruction query	$O(n)$ worst	$O(n^2)$	nxt matrix
Negative cycle detection	$O(n)$	$O(1)$	Check diagonal
Transitive closure (bitset)	$O(n^3/64)$	$O(n^2/8)$	With bitset<N>
Single edge update (recompute)	$O(n^2)$	$O(1)$	Relax all $(i,j)$ through new edge

Practical limits:

$n$	Approx ops	Time (2s TL)
200	8M	Comfortable
400	64M	Fine
500	125M	Tight but passes
700	343M	TLE

---

Problem Patterns

Pattern 1 -- Vanilla all-pairs shortest path

Compute shortest distances between all pairs. Straightforward application.

CF 295B -- Greg and Graph. Add vertices one by one, output sum of all-pairs shortest paths after each addition. Run Floyd-Warshall incrementally: when adding vertex $k$, only run the $k$-th relaxation layer.

Pattern 2 -- Transitive closure / reachability

Replace arithmetic with boolean ops. "Can person $i$ communicate with person $j$ (directly or indirectly)?"

CF 3585 (Gym) -- Determine reachability in a directed graph. Use bitset optimization for $n\le 2000$.

Pattern 3 -- Minimax / Maximin path

Change the recurrence: $d(i,j)=min(d(i,j),max(d(i,k),d(k,j)))$ for the path that minimizes the maximum edge weight (bottleneck shortest path).

CF 1204C -- Anna, Svyatoslav and Maps. Reconstruct the shortest path sequence; Floyd-Warshall to precompute all-pairs, then greedily skip intermediate waypoints.

Pattern 4 -- Counting paths of exact length

Use matrix exponentiation with Floyd-Warshall-style DP. Number of paths of length exactly $L$: multiply the adjacency matrix $L$ times in $(min,+)$ semiring for shortest paths, or $(+,\times )$ semiring for counting.

CF 21D -- Traveling Graph. Small $n$, need shortest cycle through all edges. Combine Floyd-Warshall with bitmask DP.

Pattern 5 -- Detecting negative cycles

After running Floyd-Warshall, any vertex $v$ with $d(v,v)<0$ lies on a negative cycle. Pairs $(i,j)$ where $i$ can reach such a $v$ and $v$ can reach $j$ have $d(i,j)=-\mathrm{\infty }$.

CF 472D -- Design Tutorial: Inverse the Problem. Check if a distance matrix corresponds to a tree using all-pairs checks.

Pattern 6 -- Incremental vertex insertion

Add vertices in a specific order. After inserting vertex $k$, only run the relaxation layer for $k$. Total work is still $O(n^3)$ but you get intermediate results.

CF 295B -- Greg and Graph (same as Pattern 1). Classic example of this technique.

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|  FLOYD-WARSHALL CHEAT SHEET                                      |
+------------------------------------------------------------------+
|  WHEN: all-pairs shortest path, n <= 500                         |
|  TIME: O(n^3)     SPACE: O(n^2)                                 |
+------------------------------------------------------------------+
|  INIT:                                                           |
|    dist[i][j] = INF for all i != j                               |
|    dist[i][i] = 0                                                |
|    dist[u][v] = min(dist[u][v], w)  for each edge (u,v,w)       |
+------------------------------------------------------------------+
|  CORE (k outermost!):                                            |
|    for k in [0,n):                                               |
|      for i in [0,n):                                             |
|        for j in [0,n):                                           |
|          dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])    |
+------------------------------------------------------------------+
|  GUARD OVERFLOW:                                                 |
|    if (dist[i][k] < INF && dist[k][j] < INF)                    |
|    Use INF = 1e18 (long long), NOT INT_MAX                       |
+------------------------------------------------------------------+
|  NEG CYCLE: dist[i][i] < 0 for some i                           |
|  PATH: nxt[i][j] = nxt[i][k] when relaxing                      |
|  CLOSURE: replace min/+ with OR/AND, or use bitset               |
|  MINIMAX: replace min(a, dist[i][k]+dist[k][j])                 |
|           with min(a, max(dist[i][k], dist[k][j]))              |
+------------------------------------------------------------------+

---

Gotchas & Debugging

The k-loop MUST be outermost

This is the single most common bug. If you put k as an inner loop, the DP invariant breaks and you get wrong answers silently. The order is k -> i -> j, always.

// WRONG -- will silently produce incorrect results
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++) // k must be OUTER
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

INF overflow when adding

If dist[i][k] = INF and dist[k][j] = INF, then dist[i][k] + dist[k][j] overflows. Two fixes:

1. Guard with an if: if (dist[i][k] < INF && dist[k][j] < INF)
2. Use a safe INF: const long long INF = 1e18; -- this is less than LLONG_MAX / 2, so adding two of them doesn't overflow.

Never use INT_MAX or LLONG_MAX as INF. They overflow on addition.

Self-loops

Some problems have edges from a vertex to itself with non-zero (or negative) weight. Initialize dist[i][i] = 0 and let the algorithm handle self-loops naturally. After Floyd-Warshall, dist[i][i] < 0 means vertex $i$ is on a negative cycle.

If the problem gives self-loop edges and you want the shortest self-loop (not the shortest cycle), handle it separately.

Undirected graphs

For undirected edges, set both dist[u][v] and dist[v][u]. Easy to forget one direction.

Multiple edges between same pair

Always take the minimum: dist[u][v] = min(dist[u][v], w) when reading input. Don't blindly overwrite.

int vs long long

With $n=500$ and edge weights up to ${10}^6$, the shortest path can be up to $500\times {10}^6=5\times {10}^8$, which fits in int. But with negative edges or weights up to ${10}^9$, you need long long. When in doubt, use long long.

Memory for large n

$n=500$ with long long: ${500}^2\times 8=2\text{MB}$. Fine. $n=5000$: $200\text{MB}$. Won't fit. Don't use Floyd-Warshall.

Debugging tip

Print the distance matrix after each $k$-iteration. For a graph with 4-5 vertices, you can trace by hand and spot where the bug happens.

Mental Traps

Trap 1: "Floyd-Warshall is just three nested loops -- the order doesn't matter."

The order is everything. Putting $k$ inside $i$ and $j$ mixes DP layers and silently corrupts the table. Visualize the dependency:

  CORRECT (k outermost):              WRONG (k innermost):

  Round k uses:                        Iteration (i,j,k) uses:
    d[i][k] from round k-1              d[i][k] which may already
    d[k][j] from round k-1              have been updated by some
    |                                    earlier (i', j', k') where
    v                                    k' > k but i' < i
  These are STABLE during               |
  the entire k-th round.                v
                                       INCONSISTENT -- mixes layers!

  +--------+--------+--------+         +--------+-----------------+
  | k=0    | k=1    | k=2    |         | i=0    | j=varies        |
  | layer  | layer  | layer  |         | uses   | k=0,1,...,n     |
  | builds | builds | builds |         | d[0][k]| which was       |
  | on     | on     | on     |         | already| changed when    |
  | initial| k=0    | k=1    |         | updated| processing k'>k |
  +--------+--------+--------+         +--------+-----------------+
       CLEAN layers                         CORRUPTED layers

Trap 2: "INF + INF is still INF -- no need to guard the addition."

If INF = INT_MAX (or LLONG_MAX), then INF + anything overflows to a negative number, which is less than INF. The algorithm "improves" a path to a negative distance through two unreachable nodes:

  dist[i][k] = INT_MAX    (no path i -> k)
  dist[k][j] = INT_MAX    (no path k -> j)

  dist[i][k] + dist[k][j] = INT_MAX + INT_MAX
                           = -2  (32-bit signed overflow!)
                             ^
                             |
                  This is LESS than dist[i][j] = INT_MAX
                  so the algorithm "relaxes" to -2.
                  Now dist[i][j] = -2.  WRONG!

  FIX: Either guard with:
    if (dist[i][k] < INF && dist[k][j] < INF)
  Or use INF = 1e18 (half of LLONG_MAX), so INF + INF won't overflow.

---

Self-Test

Answer without looking at the code above.

• [ ] Loop order. Write the three nested loops of Floyd-Warshall from memory. Which variable must be the outermost loop and why?
• [ ] Negative cycles. After running Floyd-Warshall, how do you detect whether a negative cycle exists? What specific array entries do you check?
• [ ] Overflow guard. Explain two different strategies to prevent integer overflow when computing dist[i][k] + dist[k][j].
• [ ] Complexity bound. What is the maximum $n$ for which Floyd-Warshall fits in a 2-second time limit? What is the memory usage for that $n$ with long long?
• [ ] Algorithm selection. You have a sparse graph with $n={10}^4$ nodes and $m=2\times {10}^4$ edges and need all-pairs shortest paths. Should you use Floyd-Warshall or Dijkstra from each source? Justify with complexity.

---

Practice Problems

CF Rating	What You Should Be Comfortable With
1200	Template Floyd-Warshall, all-pairs shortest paths, reachability matrix
1500	Negative cycle detection, shortest cycle, transitive closure, path reconstruction
1800	Floyd-Warshall on small graphs embedded in larger problems, incremental vertex addition
2100	Floyd-Warshall + bitmask DP, online Floyd-Warshall (adding vertices dynamically), algebraic generalizations (min-plus semiring)

#	Problem	Source	Difficulty	Notes
1	Greg and Graph	CF 295B	1700	Incremental Floyd-Warshall
2	Traveling Graph	CF 21D	2000	Floyd + bitmask DP
3	Anna, Svyatoslav and Maps	CF 1204C	1400	Precompute all-pairs, reconstruct
4	Design Tutorial: Inverse the Problem	CF 472D	1900	Check if dist matrix is a tree
5	Shortest Routes I	CSES	Easy	Single-source (compare with Dijkstra)
6	Shortest Routes II	CSES	Easy	Direct Floyd-Warshall application
7	Road Construction	CF 25C	1900	Merge two components, use all-pairs
8	Chamber of Secrets	CF 173B	1700	Shortest path on layered graph

---

Common Mistakes

1. Wrong loop order ($i$-$j$-$k$ instead of $k$-$i$-$j$). Your Floyd-Warshall gives wrong answers on some test cases. The code looks like:

   for (int i = 1; i <= n; i++)
       for (int j = 1; j <= n; j++)
           for (int k = 1; k <= n; k++)
               dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

   The loop order must be k (intermediate vertex) as the outermost loop. When $k$ is innermost, you check all possible "midpoints" for each pair without guaranteeing that the intermediate paths are already optimal. The correct order is for (int k ...) for (int i ...) for (int j ...). This is THE classic Floyd-Warshall mistake. Burn k-i-j into your memory.

Debug Drills

Drill 1. Floyd-Warshall runs correctly but path reconstruction fails:

int next[N][N];
// initialization: next[i][j] = j if edge exists, else -1
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
                next[i][j] = next[i][j];  // BUG!
            }

What's wrong?

When the shortest path from $i$ to $j$ is updated to go through $k$, the next hop from $i$ should be the next hop from $i$ to $k$ (not $i$ to $j$, which is unchanged). Fix: next[i][j] = next[i][k].

Drill 2. Negative cycle detection gives false positives:

// After Floyd-Warshall:
for (int i = 1; i <= n; i++)
    if (dist[i][i] < 0)
        cout << "Negative cycle exists!\n";

What's wrong?

This is actually correct -- if dist[i][i] < 0, then there's a cycle from $i$ back to $i$ with negative total weight. The issue might be overflow: if dist[i][k] + dist[k][j] overflows (both near INF), it could produce a small or negative number. Fix: guard the update with if (dist[i][k] < INF && dist[k][j] < INF).

Drill 3. Floyd-Warshall gives wrong answer for transitive closure:

bool reach[N][N];
// initialize: reach[i][j] = true if edge (i,j) exists
// reach[i][i] = true
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
// But reach[3][5] is false when there's clearly a path 3->7->5

What's wrong?

The logic is correct for Floyd-Warshall transitive closure. If reach[3][5] is still false, the likely issue is initialization: did you initialize reach[i][j] = true for ALL existing edges? Common mistake: for undirected graphs, only setting reach[u][v] but not reach[v][u]. Also verify reach[i][i] = true for all $i$.

---

Further Reading

• cp-algorithms: Floyd-Warshall -- Detailed proof and variants.
• CF Blog: All-Pairs Shortest Path -- Community discussion and tricks.
• CSES Graph Section -- Practice problems with test cases.
• Competitive Programmer's Handbook, Ch. 13 -- Concise coverage of Floyd-Warshall.
• Related in this guidebook: Dijkstra's Algorithm, Bellman-Ford, Graph Representation.

---