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

TL;DR: Floyd-Warshall tìm đường ngắn nhất giữa mọi cặp đỉnh (all-pairs shortest path) bằng quy hoạch động (DP), trong đó chiều thứ ba là "đỉnh trung gian 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, lõi chỉ vài dòng code. So với chạy Dijkstra V lần, nó xử lý được cạnh âm, code đơn giản hơn, và tốt hơn khi graph dense hoặc V nhỏ (dưới 500). Phát hiện negative cycle bằng cách kiểm tra dist[i][i] < 0 sau khi chạy xong.

Dijkstra tìm đường ngắn nhất từ một source đến mọi vertex trong O((V+E) log V). Bellman-Ford làm tương tự nhưng xử lý được cạnh âm, trong O(V × E). Nhưng cả hai chỉ giải single-source shortest path, tức từ một đỉnh đến tất cả các đỉnh còn lại.

Nhiều bài toán thực tế cần all-pairs shortest path, tức đường ngắn nhất giữa mọi cặp vertex. Ví dụ: datacenter cần bảng độ trễ giữa tất cả các node; sàn forex cần tỷ giá đổi tốt nhất giữa mọi cặp tiền tệ; social network cần biết user nào đến được user nào. Một cách giải là chạy Dijkstra V lần, tổng O(V × (V+E) log V). Cách khác là Floyd-Warshall: 3 vòng lặp lồng nhau, O(V³), code vài dòng, xử lý cạnh âm sẵn.

Bài này dạy Floyd-Warshall: DP theo đỉnh trung gian k, vì sao cập nhật tại chỗ trên mảng 2D vẫn đúng, khi nào chọn FW thay cho V × Dijkstra, và biến thể transitive closure (bao đóng bắc cầu).

1. Hình dung: Bảng khoảng cách thành phố

Hình dung bạn có bảng khoảng cách trực tiếp giữa các thành phố: Hà Nội → TP.HCM 1700 km (đường bộ, số làm tròn), Hà Nội → Đà Nẵng 800 km, Đà Nẵng → TP.HCM 950 km.

Câu hỏi: đi từ Hà Nội đến TP.HCM có ngắn hơn nếu ghé Đà Nẵng không? Kiểm tra: dist[HN][DN] + dist[DN][HCM] = 800 + 950 = 1750 > 1700, không ngắn hơn.

Lặp lại phép 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. Thử hết mọi c, ta được bảng khoảng cách tốt nhất giữa mọi cặp thành phố. Đó chính là Floyd-Warshall.

2. DP formulation — Intermediate vertex k

2.1 State definition

Định nghĩa dp[k][i][j] là độ dài đường ngắn nhất từ i đến j mà chỉ dùng các vertex trong tập {0, 1, ..., k} làm đỉnh trung gian (đỉnh trung gian là đỉnh đi ngang qua, không phải điểm đầu hay điểm cuối).

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.

Công thức chuyển (thêm vertex k vào tập đỉnh trung gian):

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³) bộ nhớ. Ta thu gọn được về 2D:

dp[i][j] <- min(dp[i][j], dp[i][k] + dp[k][j])    -- cập nhật in-place

Vì sao cập nhật tại chỗ (in-place) vẫn đúng? Khi cập nhật dp[i][j] với đỉnh trung gian k, ta dùng dp[i][k] và dp[k][j]. Vậy các giá trị này có bị đổi ngay trong vòng lặp k hiện tại không?

• (Giả sử không có negative cycle.) dp[k][k] là đường ngắn nhất từ k về k qua các đỉnh trung gian trong tập {0..k}. Path đơn giản nhất là đứng yên tại k (độ dài 0), nên dp[k][k] = 0 và không đổi khi thêm k vào tập đỉnh trung gian.
• dp[i][k] là path từ i đến k qua các đỉnh trung gian trong {0..k}. Nếu cập nhật dp[i][k] theo công thức trên: min(dp[i][k], dp[i][k] + dp[k][k]) = min(dp[i][k], dp[i][k] + 0) = dp[i][k], tức không đổi.
• dp[k][j] cũng không đổi, lý do tương tự.

Vậy dp[i][k] và dp[k][j] giữ nguyên giá trị của bước k-1 dù cập nhật tại chỗ, nên thuật toán 2D cho kết quả đúng.

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²)

Ba vòng for lồng nhau, mỗi vòng chạy V lần, nên V × V × V; cách đếm này giống bài Lặp lồng nhau.

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][2] + dist[2][3] = 4 + 9 = 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 ra? 3 vòng lặp lồng nhau, mỗi vòng chạy V lần, tổng V × V × V thao tác, mỗi thao tác O(1).

Bộ nhớ O(V²): chỉ cần ma trận dist[V][V].

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

• Dense graph (E ≈ V²): V × Dijkstra dùng binary heap = O(V × V² log V) = O(V³ log V), chậm hơn FW (Dijkstra bản mảng O(V²) mỗi lần thì cùng bậc V³).
• V nhỏ (dưới 500): V³ = 125 triệu thao tác, chạy trong vài trăm mili giây.
• Có cạnh âm: Dijkstra sai, FW xử lý được.
• Code đơn giản hơn nhiều: vài dòng lặp, thay vì Dijkstra cộng thêm vòng lặp ngoài và các biến phụ.

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 hẳn O(V³).
• V lớn (vượt 500-1000): V³ trở nên quá đắt.
• Không có cạnh âm.

5. Floyd-Warshall vs V × Dijkstra

6. Variants

6.1 Transitive closure — Warshall's algorithm

Thay vì tìm đường ngắn nhất, đôi khi chỉ cần biết "có path từ i đến j không?". Khi đó dùng ma trận boolean:

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: kiểm tra đến được hay không trong graph có hướng, giải dependency, "bạn của bạn" trong social network.

6.2 Path reconstruction

Ghi thêm next[i][j], là vertex kế tiếp 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

-- Dựng lại 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 vì tìm path có tổng nhỏ nhất, ta tìm path có "nút thắt cổ chai" (bottleneck) lớn nhất, tức path mà cạnh nhỏ nhất trên đó 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: routing mạng theo băng thông, truyền tải điện với công suất tối đa.

7. Bẫy tổng hợp

Bẫy 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ộ ma trận dist để tránh hẳn overflow.

Bẫy 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ẽ thành số âm (thuật toán cứ giảm dist[i][i] qua cycle). Nơi nhận kết quả sẽ dùng giá trị sai hoàn toàn: cost âm vô nghĩa, routing chọn sai, NPC đi vòng mãi. Luôn kiểm tra dist[i][i] < 0 sau khi chạy xong.

Bẫy 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 trường hợp cơ sở, nghĩa là "đứng yên tại i thì cost bằng 0". Nếu khởi tạo sai, mọi path đi qua i làm đỉnh trung gian đều bị ảnh hưởng. Hãy kiểm tra input hoặc ép dist[i][i] = 0 ở bước khởi tạo.

8. Path reconstruction — pseudocode đầy đủ

Ghép mảng next ở mục 6.2 vào bản ở mục 3 như sau: khởi tạo next[i][j] = j với mỗi cạnh i → j, và ở dòng cập nhật dist[i][j] qua k thì thêm next[i][j] <- next[i][k]. Phần còn lại (vòng k, i, j, guard INF, kiểm tra dist[i][i] < 0) giữ nguyên, vẫn O(V³) time và O(V²) space.

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

Kỹ sư mạng, bảng độ trễ giữa mọi cặp node: datacenter cần bảng độ trễ giữa mọi cặp node để quyết định routing. Với V = 50 node, V³ = 125.000 thao tác, chạy chỉ cỡ trăm micro-giây đến vài mili-giây. Bảng dist[50][50] kết quả dùng làm bảng tra cho mọi request routing, khỏi tính lại mỗi lần.

Sàn forex, tỷ giá tốt nhất giữa mọi cặp: cần tỷ giá đổi tốt nhất giữa mọi cặp trong cỡ vài trăm đơn vị tiền tệ. Với trọng số -log(rate) như bài Bellman-Ford, tính trước toàn bộ bảng khoảng cách (mỗi lần tỷ giá đổi thì tính lại) rồi trả kết quả từ bộ nhớ. Nếu bảng tỷ giá có arbitrage thì graph có negative cycle và kết quả vô nghĩa, nên phải kiểm tra dist[i][i] < 0 trước.

Social network, transitive closure: "bạn của bạn", tức kiểm tra user A có đến được user B hay không. Dùng thuật toán Warshall trên một subgraph (V thường nhỏ sau khi lọc theo cộng đồng). Ứng dụng: gợi ý kết bạn, kiểm soát truy cập ("user này có thuộc team của người duyệt không?").

AI trên bản đồ game nhỏ: với lưới nhỏ V dưới 50, tính trước khoảng cách giữa mọi cặp một lần khi load map. NPC tra dist[current][target] trong O(1) cho mọi quyết định tìm đường, không cần chạy A* mỗi frame.

10. Đào sâu

11. Tóm tắt

• Floyd-Warshall tìm đường ngắn nhất giữa mọi cặp đỉnh bằng DP theo đỉnh trung gian k: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]), ba vòng lặp lồng nhau, O(V³) time, O(V²) space.
• Cập nhật tại chỗ trên mảng 2D vẫn đúng vì dp[i][k] và dp[k][j] không đổi trong vòng lặp k (xuất phát từ dp[k][k] = 0).
• Xử lý được cạnh âm, phát hiện negative cycle bằng dist[i][i] < 0.
• FW thắng V × Dijkstra khi graph dense, V nhỏ (dưới 500), hoặc có cạnh âm. Biến thể Warshall dùng ma trận boolean cho transitive closure.
• Chặn INF trước khi cộng để không làm hỏng cả ma trận.

12. Tự kiểm tra

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