Floyd-Warshall — All-pairs shortest path qua DP-on-graph

Dijkstra tìm shortest path từ một source đến mọi vertex trong O((V+E) log V). Bellman-Ford làm tương tự với hỗ trợ negative edge trong O(V × E). Nhưng cả hai chỉ giải single-source shortest path — từ một đỉnh đến tất cả các đỉnh còn lại.

Bài toán thực tế hay cần hơn: all-pairs shortest path — shortest path giữa mọi cặp vertex. Ví dụ: datacenter cần bảng latency giữa tất cả các node; forex broker cần best conversion rate giữa mọi cặp tiền tệ; social network cần reachability giữa mọi cặp user. Một cách giải: chạy Dijkstra V lần, tổng O(V × (V+E) log V). Hoặc dùng Floyd-Warshall: 3 nested loop, O(V³), code 5 dòng, hỗ trợ negative edge sẵn.

Bài này dạy Floyd-Warshall: DP với intermediate vertex k, chứng minh tại sao in-place 2D đúng, khi nào chọn FW thay V × Dijkstra, và transitive closure variant.

1. Analogy — Bảng khoảng cách thành phố

Hãy tưởng tượng bạn có một bảng khoảng cách trực tiếp giữa các thành phố: Hà Nội → TP.HCM 1200 km, Hà Nội → Đà Nẵng 800 km, Đà Nẵng → TP.HCM 950 km.

Câu hỏi: đường từ Hà Nội đến TP.HCM có rút ngắn được qua Đà Nẵng không? Kiểm tra: dist[HN][DN] + dist[DN][HCM] = 800 + 950 = 1750 > 1200 — không ngắn hơn.

Lặp lại kiểm tra này với mọi thành phố trung gian c, cho mọi cặp (a, b): nếu dist[a][c] + dist[c][b] < dist[a][b] thì cập nhật. Sau khi thử mọi c — ta có bảng khoảng cách tốt nhất giữa mọi cặp thành phố. Đây chính xác là Floyd-Warshall.

2. DP formulation — Intermediate vertex k

2.1 State definition

Định nghĩa dp[k][i][j] = độ dài shortest path từ i đến j chỉ sử dụng các vertex {0, 1, ..., k} làm intermediate (đỉnh trung gian — không phải start hay end, mà là các đỉnh đi qua).

Base case (k = -1, không có intermediate):

• dp[-1][i][j] = weight của edge trực tiếp i → j (vô cùng nếu không có cạnh).
• dp[-1][i][i] = 0 cho mọi i.

Transition (thêm vertex k vào tập intermediate):

dp[k][i][j] = min(
    dp[k-1][i][j],           // khong di qua k
    dp[k-1][i][k] + dp[k-1][k][j]  // di qua k
)

Final answer: dp[V-1][i][j] cho mọi cặp (i, j).

2.2 Space optimization — 2D in-place

Mảng 3D dp[V][V][V] tốn O(V³) không gian. Ta có thể reduce về 2D:

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])  // update in-place

Tại sao in-place vẫn correct? Câu hỏi: khi update dp[i][j] với intermediate k, ta dùng dp[i][k] và dp[k][j] — nhưng các giá trị này có bị update trong vòng lặp k hiện tại không?

• dp[k][k] = shortest path từ k đến k qua intermediate trong tập {0..k}. Vì path đơn giản nhất là ở lại k (độ dài 0), dp[k][k] = 0 — không thay đổi khi thêm k vào intermediate.
• dp[i][k]: path từ i đến k qua intermediate trong {0..k}. Nếu ta update dp[i][k] với formula trên: min(dp[i][k], dp[i][k] + dp[k][k]) = min(dp[i][k], dp[i][k] + 0) = dp[i][k] — không thay đổi.
• Tương tự dp[k][j] không thay đổi.

Vậy dp[i][k] và dp[k][j] giữ nguyên giá trị từ k-1, dù update in-place. Thuật toán 2D correct.

3. Code Java

public class FloydWarshall {

    // graph[i][j] = edge weight from i to j.
    // Use Integer.MAX_VALUE to represent no direct edge.
    // graph[i][i] must be 0.
    public static int[][] floydWarshall(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            dist[i] = graph[i].clone();
        }

        // Try each vertex k as intermediate
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // Guard: skip if i->k or k->j is unreachable (avoid overflow)
                    if (dist[i][k] == Integer.MAX_VALUE
                            || dist[k][j] == Integer.MAX_VALUE) continue;

                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // Detect negative cycle: dist[i][i] < 0
        for (int i = 0; i < n; i++) {
            if (dist[i][i] < 0) {
                throw new IllegalStateException("Negative cycle detected");
            }
        }

        return dist;
    }
}

3.1 Trace ví dụ — graph 4 vertex

Graph directed weighted:

0 ---(3)--> 1
|           |
(8)        (-4)
|           v
3 <--(1)-- 2 <--(2)-- 0
    also: 1->(7)->3, 2->(5)->0, 3->(4)->0

Sử dụng graph kinh điển từ CLRS (đơn giản hóa):

     0    1    2    3
0  [ 0,   3,  INF,  7]
1  [INF,  0,   4, INF]
2  [ 2, INF,   0, INF]
3  [INF,  1,  INF,  0]

Edges: 0→1 w3, 0→3 w7, 1→2 w4, 2→0 w2, 3→1 w1.

Sau k=0 (thêm vertex 0 làm intermediate):

• dist[2][1]: hiện INF. Qua 0: dist[2][0] + dist[0][1] = 2 + 3 = 5. Cập nhật 5.
• dist[2][3]: hiện INF. Qua 0: dist[2][0] + dist[0][3] = 2 + 7 = 9. Cập nhật 9.

Sau k=1 (thêm vertex 1):

• dist[0][2]: hiện INF. Qua 1: dist[0][1] + dist[1][2] = 3 + 4 = 7. Cập nhật 7.
• dist[2][2]: hiện 0. Qua 1: dist[2][1] + dist[1][2] = 5 + 4 = 9. Giữ 0.
• dist[3][2]: hiện INF. Qua 1: dist[3][1] + dist[1][2] = 1 + 4 = 5. Cập nhật 5.

Sau k=2 (thêm vertex 2):

• dist[0][0]: hiện 0. Qua 2: dist[0][2] + dist[2][0] = 7 + 2 = 9. Giữ 0.
• dist[1][0]: hiện INF. Qua 2: dist[1][2] + dist[2][0] = 4 + 2 = 6. Cập nhật 6.
• dist[3][0]: hiện INF. Qua 2: dist[3][2] + dist[2][0] = 5 + 2 = 7. Cập nhật 7.

Sau k=3 (thêm vertex 3):

• dist[0][1]: hiện 3. Qua 3: dist[0][3] + dist[3][1] = 7 + 1 = 8. Giữ 3.
• dist[1][1]: hiện 0. Qua 3: dist[1][3] = INF. Skip.
• dist[2][1]: hiện 5. Qua 3: dist[2][3] + dist[3][1] = 9 + 1 = 10. Giữ 5.

Kết quả cuối:

     0    1    2    3
0  [ 0,   3,   7,   7]
1  [ 6,   0,   4,  11]
2  [ 2,   5,   0,   9]
3  [ 7,   1,   5,   0]

Không có dist[i][i] < 0 → không có negative cycle.

4. Complexity

O(V³) từ đâu? 3 nested loop, mỗi loop chạy V lần — V × V × V operations, mỗi operation O(1).

O(V²) space: chỉ cần ma trận dist[V][V].

Khi nào Floyd-Warshall thắng V × Dijkstra?

• Dense graph (E ≈ V²): V × Dijkstra = O(V × V² log V) = O(V³ log V) — chậm hơn FW.
• V nhỏ (V ≤ 500): V³ = 125 triệu operations, chạy trong vài trăm milliseconds.
• Cần hỗ trợ negative edge: Dijkstra fail, FW xử lý được.
• Code đơn giản hơn nhiều: 5 dòng loop vs Dijkstra + outer loop + bookkeeping.

Khi nào V × Dijkstra thắng?

• Sparse graph (E nhỏ hơn nhiều so với V²): O(V × (V+E) log V) nhỏ hơn nhiều so với O(V³).
• V lớn (V vượt 500-1000): V³ trở nên quá tốn kém.
• Không có negative edge.

5. Floyd-Warshall vs V × Dijkstra

6. Variants

6.1 Transitive closure — Warshall's algorithm

Thay tìm shortest path, chỉ cần biết "có path từ i đến j không?". Dùng boolean matrix:

// reach[i][j] = true if j is reachable from i
boolean[][] warshall(boolean[][] reach) {
    int n = reach.length;
    boolean[][] r = new boolean[n][n];
    for (int i = 0; i < n; i++) r[i] = reach[i].clone();

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                r[i][j] = r[i][j] || (r[i][k] && r[k][j]);
    return r;
}

Dùng cho: directed reachability, dependency resolution, social network "bạn của bạn".

6.2 Path reconstruction

Theo dõi thêm next[i][j] = vertex tiếp theo trên path từ i đến j:

int[][] next = new int[n][n];
// Init: next[i][j] = j if direct edge exists, else -1
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        next[i][j] = (graph[i][j] != Integer.MAX_VALUE && i != j) ? j : -1;

// In the main loop, also update next:
// if (dist[i][k] + dist[k][j] < dist[i][j]) {
//     dist[i][j] = dist[i][k] + dist[k][j];
//     next[i][j] = next[i][k];   // go through k first
// }

// Reconstruct path from src to dst:
List<Integer> getPath(int[][] next, int src, int dst) {
    if (next[src][dst] == -1) return List.of(); // no path
    List<Integer> path = new ArrayList<>();
    path.add(src);
    while (src != dst) {
        src = next[src][dst];
        path.add(src);
    }
    return path;
}

6.3 Maximum bandwidth path

Thay tìm min-sum path, tìm path có bottleneck lớn nhất — "path mà cạnh nhỏ nhất là lớn nhất nhất có thể":

// bandwidth[i][j]: max min-edge weight from i to j
// Transition: bandwidth[i][j] = max(bandwidth[i][j],
//                                   min(bandwidth[i][k], bandwidth[k][j]))

Dùng cho: network routing theo bandwidth, cable tải tải điện max.

7. Pitfall tổng hợp

Pitfall 1 — Overflow khi cộng hai giá trị Integer.MAX_VALUE:

// BUG: dist[i][k] = Integer.MAX_VALUE, dist[k][j] = 5
// Integer.MAX_VALUE + 5 overflows to negative number
if (dist[i][k] + dist[k][j] < dist[i][j]) { // overflow -> always true!
    dist[i][j] = dist[i][k] + dist[k][j];    // corrupts dist matrix
}

// CORRECT: guard unreachable paths before addition
if (dist[i][k] == Integer.MAX_VALUE || dist[k][j] == Integer.MAX_VALUE) continue;
if (dist[i][k] + dist[k][j] < dist[i][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
}

Hoặc dùng long cho toàn bộ dist matrix để tránh overflow hoàn toàn.

Pitfall 2 — Quên kiểm tra negative cycle:

// BUG: return dist without checking
return dist; // if negative cycle exists, dist[i][i] < 0
             // consumer uses garbage values without knowing

Nếu graph có negative cycle, dist[i][i] sẽ trở thành âm (algorithm giảm dist[i][i] qua cycle). Consumer nhận kết quả sai hoàn toàn — path cost âm vô nghĩa, routing quyết định sai, NPC đi vòng lặp mãi. Luôn check dist[i][i] < 0 sau khi chạy xong.

Pitfall 3 — Input matrix không init dist[i][i] = 0:

// BUG: caller passes matrix with dist[i][i] = INF instead of 0
// Every path i -> ... -> i will be computed as INF + something = wrong
// dist[i][j] for all j will remain inflated or INF

Floyd-Warshall dựa vào dist[i][i] = 0 làm base case — "cost đứng tại i là 0". Nếu init sai, mọi path đi qua i làm intermediate sẽ bị ảnh hưởng. Kiểm tra input hoặc force dist[i][i] = 0 ở bước khởi tạo.

8. Path reconstruction — code hoàn chỉnh

public class FloydWarshallWithPath {

    public static int[][] dist;
    public static int[][] next;

    public static void compute(int[][] graph) {
        int n = graph.length;
        dist = new int[n][n];
        next = new int[n][n];

        // Initialize dist and next
        for (int i = 0; i < n; i++) {
            dist[i] = graph[i].clone();
            for (int j = 0; j < n; j++) {
                if (i != j && graph[i][j] != Integer.MAX_VALUE) {
                    next[i][j] = j;
                } else {
                    next[i][j] = -1;
                }
            }
        }

        // Main DP 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] == Integer.MAX_VALUE
                            || dist[k][j] == Integer.MAX_VALUE) continue;

                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k]; // route through k first
                    }
                }
            }
        }

        // Check negative cycle
        for (int i = 0; i < n; i++) {
            if (dist[i][i] < 0) {
                throw new IllegalStateException("Negative cycle detected");
            }
        }
    }

    public static List<Integer> getPath(int src, int dst) {
        if (next[src][dst] == -1) return List.of(); // no path
        List<Integer> path = new ArrayList<>();
        path.add(src);
        int cur = src;
        while (cur != dst) {
            cur = next[cur][dst];
            if (cur == -1) return List.of(); // should not happen if no negative cycle
            path.add(cur);
        }
        return path;
    }
}

9. Ứng dụng thực tế

Network engineer — all-pairs latency table: datacenter cần bảng latency giữa mọi cặp node để routing decision. Với V = 50 node, V³ = 125.000 operations — chạy trong microseconds. Kết quả: bảng dist[50][50] dùng làm lookup table cho mọi routing request mà không cần recompute mỗi lần.

Forex broker — all-pairs conversion rate: cần hiển thị best conversion rate giữa mọi cặp trong 170 đơn vị tiền tệ. Thay vì query mỗi cặp riêng, pre-compute toàn bộ dist[170][170] offline (mỗi lần rate thay đổi) và serve từ in-memory lookup. Với maximum bandwidth variant, tìm path có bottleneck conversion rate cao nhất.

Social network — transitive closure: "bạn của bạn" — kiểm tra user A có reachable đến user B trong k hops không. Dùng Warshall's algorithm trên subgraph (V thường nhỏ sau khi filter bởi community). Ứng dụng: friend suggestion, access control ("user này có trong team của người duyệt không?").

Game map AI — small grid pathfinding: grid nhỏ V ≤ 50, pre-compute all-pairs distances một lần khi load map. NPC có thể lookup dist[current][target] trong O(1) cho mọi quyết định pathfinding — không cần chạy A* mỗi frame.

10. Deep Dive

11. Tóm tắt

• Floyd-Warshall giải all-pairs shortest path bằng DP với dimension "intermediate vertex k": dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]).
• 3 nested loop O(V³): thử mọi k làm trạm trung gian cho mọi cặp (i, j).
• In-place 2D correct vì dp[i][k] và dp[k][j] không thay đổi trong vòng lặp k — proof từ dp[k][k] = 0.
• Negative edge xử lý được — không có giả định greedy như Dijkstra.
• Detect negative cycle bằng kiểm tra dist[i][i] < 0 sau khi chạy xong.
• FW thắng V × Dijkstra khi graph dense (E ≈ V²), V nhỏ (≤ 500), hoặc cần negative edge support.
• Warshall variant dùng boolean matrix cho transitive closure — directed reachability, "bạn của bạn".
• Guard Integer.MAX_VALUE trước khi cộng để tránh overflow corrupt toàn bộ dist matrix.

12. Tự kiểm tra

Bài tiếp theo: MST — Kruskal vs Prim