25. Floyd-Warshall

What you'll learn

• 1Implement Floyd-Warshall (3-line core)
• 2Understand the DP recurrence
• 3Detect negative cycles via the diagonal

Overview

For each intermediate vertex k, see if using k as a way-point shortens the path from i to j. O(V³) — fine for V ≤ 500, infeasible beyond that.

Core Concepts

1. The algorithm

def floyd_warshall(n, edges):
    INF = float('inf')
    dist = [[INF] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

2. DP recurrence

dp[k][i][j] = shortest path from i to j using only vertices in {1,..,k} as intermediates. Recurrence: dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]).

We compress the first dimension into the same dist[i][j] table since the recurrence allows it.

3. Detecting negative cycles

for i in range(1, n + 1):
    if dist[i][i] < 0:
        print('Negative cycle detected!')
        return

4. When to use FW vs Dijkstra

Examples

Example 1 — src/01_floyd.py

Floyd-Warshall — BOJ 11404 (Floyd).

Example 2 — src/02_negative_cycle.py

Negative cycle detection.

Example 3 — src/03_transitive_closure.py

Transitive closure — boolean version of FW.

Example 4 — src/04_path_reconstruct.py

Reconstruct the actual shortest path.

Common Mistakes

1. Wrong loop order — `for k` MUST be the outermost loop.
2. Forgetting to initialize dist[i][i] = 0.
3. Running on graphs with V > 500 — TLE.
4. Allowing duplicates of (u, v) without taking the min.

Recap

• Floyd-Warshall: 3 nested loops, k outermost.
• O(V³) — small dense graphs only.
• Handles negative weights (not negative cycles).

Try It

1. BOJ 11404 (Floyd).
2. BOJ 1389 (Kevin Bacon's six degrees).