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

TL;DR: Floyd-Warshall giải bài toán all-pairs shortest path bằng DP với dimension "intermediate vertex k": thử từng đỉnh k làm trạm trung gian, cập nhật dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) cho mọi cặp (i, j). Ba vòng lặp lồng nhau, O(V³) time, O(V²) space, 5 dòng code cốt lõi. Ưu điểm so với V × Dijkstra: hỗ trợ negative edge, code đơn giản hơn, tốt hơn khi graph dense hoặc V nhỏ (dưới 500). Phát hiện negative cycle bằng kiểm tra dist[i][i] < 0 sau khi chạy xong.

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],                    -- không đi qua k
    dp[k-1][i][k] + dp[k-1][k][j]    -- đi 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])    -- cập nhật 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. Pseudocode

FloydWarshall(G, n):
    -- Khởi tạo ma trận khoảng cách từ ma trận kề
    dist[0..n-1][0..n-1] <- G   -- sao chép trọng số cạnh
    dist[i][i] <- 0  với mọi i
    dist[i][j] <- INF nếu không có cạnh i->j

    -- Vòng lặp chính: thử từng đỉnh k làm trung gian
    for k <- 0 đến n-1:
        for i <- 0 đến n-1:
            for j <- 0 đến n-1:
                if dist[i][k] = INF hoặc dist[k][j] = INF:
                    continue          -- không thể đi qua k
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] <- dist[i][k] + dist[k][j]

    -- Phát hiện chu trình âm
    for i <- 0 đến n-1:
        if dist[i][i] < 0:
            báo lỗi "Có chu trình âm"

    return dist

Time: O(V³) Space: O(V²)

flowchart TD
    INIT["Khởi tạo dist từ ma trận kề\ndist[i][i] = 0, dist[i][j] = INF nếu không có cạnh"]
    OUTER["Vòng k = 0..n-1\n(thử đỉnh k làm trung gian)"]
    INNER["Với mỗi cặp (i, j):\nnếu dist[i][k] + dist[k][j] < dist[i][j]\n→ cập nhật dist[i][j]"]
    CHECK["Kiểm tra dist[i][i] < 0\nvới mọi i"]
    DONE["Trả về ma trận dist\n(all-pairs shortest path)"]
    NEG["Báo lỗi: chu trình âm"]

    INIT --> OUTER
    OUTER --> INNER
    INNER --> OUTER
    OUTER -- "đã xét hết k" --> CHECK
    CHECK -- "có dist[i][i] < 0" --> NEG
    CHECK -- "không có" --> DONE

3.1 Trace ví dụ — graph 4 vertex

Graph directed weighted:

     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[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[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.
• dist[1][3]: hiện INF. Qua 2: dist[1][0] + dist[0][3] = 6 + 7 = 13. Cập nhật 13.

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[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,  13]
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 dưới 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:

Warshall(reach, n):
    -- reach[i][j] = true nếu j có thể tới từ i
    r[0..n-1][0..n-1] <- reach    -- sao chép

    for k <- 0 đến n-1:
        for i <- 0 đến n-1:
            for j <- 0 đến n-1:
                r[i][j] <- r[i][j] hoặc (r[i][k] và r[k][j])

    return r

Time: O(V³) Space: O(V²)

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:

-- Khởi tạo: next[i][j] = j nếu có cạnh trực tiếp, ngược lại = NIL
-- Trong vòng lặp chính, nếu cập nhật dist[i][j] qua k:
--   next[i][j] <- next[i][k]    -- đi qua k trước

-- Reconstruct path từ src đến dst:
GetPath(next, src, dst):
    if next[src][dst] = NIL: return []    -- không có đường
    path <- [src]
    cur <- src
    while cur != dst:
        cur <- next[cur][dst]
        path.append(cur)
    return path

Time: O(V) Space: O(V²) cho mảng next

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 có thể":

-- bandwidth[i][j] = băng thông tối đa trên path từ i đến j
-- Transition:
bandwidth[i][j] <- max(bandwidth[i][j],
                        min(bandwidth[i][k], bandwidth[k][j]))

Dùng cho: network routing theo bandwidth, đường truyền tải điện cực đại.

7. Pitfall tổng hợp

Pitfall 1 — Overflow khi cộng hai giá trị INF

-- BUG: dist[i][k] = INF, dist[k][j] = 5
-- INF + 5 tràn số -> số âm -> luôn nhỏ hơn dist[i][j] -> sai
if dist[i][k] + dist[k][j] < dist[i][j]:
    dist[i][j] <- dist[i][k] + dist[k][j]    -- dist matrix bị hỏng

-- CORRECT: kiểm tra trước khi cộng
if dist[i][k] = INF hoặc dist[k][j] = INF:
    continue    -- không thể đi qua k, bỏ qua
if dist[i][k] + dist[k][j] < dist[i][j]:
    dist[i][j] <- dist[i][k] + dist[k][j]

Time: O(V³) Space: O(V²)

Hoặc dùng kiểu số 64-bit cho toàn bộ dist matrix để tránh overflow hoàn toàn.

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

-- BUG: trả về dist mà không kiểm tra
return dist
-- nếu có negative cycle, dist[i][i] < 0
-- caller dùng giá trị sai hoàn toàn mà không biết

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 truyền matrix với dist[i][i] = INF thay vì 0
-- Mọi path i -> ... -> i tính ra INF + something = sai
-- dist[i][j] với mọi j sẽ bị phình lên hoặc giữ 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 — pseudocode đầy đủ

FloydWarshallWithPath(G, n):
    dist[0..n-1][0..n-1] <- G
    next[0..n-1][0..n-1] <- NIL

    -- Khởi tạo next: next[i][j] = j nếu có cạnh i->j
    for i <- 0 đến n-1:
        dist[i][i] <- 0
        for j <- 0 đến n-1:
            if i != j và G[i][j] != INF:
                next[i][j] <- j

    -- Vòng lặp chính
    for k <- 0 đến n-1:
        for i <- 0 đến n-1:
            for j <- 0 đến n-1:
                if dist[i][k] = INF hoặc dist[k][j] = INF:
                    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]    -- đi qua k trước

    -- Kiểm tra chu trình âm
    for i <- 0 đến n-1:
        if dist[i][i] < 0:
            báo lỗi "Có chu trình âm"

    return dist, next

Time: O(V³) Space: O(V²)

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 dưới 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ỏ (dưới 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 INF 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