Floyd-Warshall — Bậc thầy All-Pairs

Dijkstra tìm shortest path từ một nguồn. Bellman-Ford xử lý thêm trọng số âm. Nhưng khi bạn cần khoảng cách giữa mọi cặp đỉnh — routing table trong network, ma trận kết nối giữa các thành phố, hoặc precompute pathfinding cho game — Floyd-Warshall là lựa chọn đơn giản và mạnh mẽ nhất.

Ba vòng for lồng nhau, bốn dòng logic cốt lõi, nhưng giải quyết hoàn chỉnh bài toán all-pairs shortest path — kể cả trọng số âm và phát hiện chu trình âm. Đây là một trong những thuật toán có tỷ lệ "sức mạnh / độ phức tạp cài đặt" cao nhất trong khoa học máy tính.

Bức tranh tư duy

Hình dung bạn quản lý mạng lưới giao thông giữa V thành phố. Ban đầu, bạn chỉ biết đường bay trực tiếp. Bạn muốn tìm đường rẻ nhất giữa mọi cặp thành phố — kể cả đường quá cảnh.

Cách tiếp cận: thử từng thành phố làm trạm trung chuyển. Vòng $k=0$: xét quá cảnh qua thành phố 0 — có rẻ hơn bay thẳng không? Vòng $k=1$: thêm thành phố 1 vào tập trung chuyển. Cứ thế cho đến vòng $k=V-1$.

Ban đầu: chỉ biết đường thẳng
    A --3-- B         dist[A][C] = ∞ (không có đường thẳng)
    |       |
    7       2
    |       |
    D --1-- C

Sau k=1 (thêm B làm trung chuyển):
    dist[A][C] = min(∞, dist[A][B] + dist[B][C])
               = min(∞, 3 + 2) = 5         ← tìm đường qua B!

Sau k=3 (thêm D):
    dist[A][C] = min(5, dist[A][D] + dist[D][C])
               = min(5, 7 + 1) = 5         ← đường cũ vẫn tốt hơn

Bản chất: Floyd-Warshall là dynamic programming trên tập đỉnh trung gian được phép sử dụng.

Cốt lõi kỹ thuật

Công thức DP

dp[k][i][j] = shortest path từ i đến j, chỉ dùng đỉnh {0, 1, ..., k} làm 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
)

Vì dp[k] chỉ phụ thuộc dp[k-1], ta tối ưu không gian xuống 2D: cập nhật trực tiếp trên dist[i][j].

Điều kiện tiên quyết: vòng k phải ở ngoài cùng. Đặt k ở vòng trong sẽ cho thuật toán khác và kết quả sai.

Cài đặt chuẩn

C++

#include <vector>
#include <climits>
using namespace std;

const int INF = 1e9;

// dist: V×V adjacency matrix. dist[i][j] = weight hoặc INF nếu không có cạnh
void floydWarshall(vector<vector<int>>& dist) {
    int V = dist.size();

    for (int k = 0; k < V; ++k)
        for (int i = 0; i < V; ++i)
            for (int j = 0; j < V; ++j)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

Python

def floyd_warshall(dist: list[list[float]]) -> list[list[float]]:
    """
    All-pairs shortest path. Modifies dist in-place.
    dist[i][j] = weight of edge i→j, or float('inf') if no edge.
    dist[i][i] = 0.
    Time: O(V³), Space: O(V²) for the matrix.
    """
    V = len(dist)
    INF = float('inf')

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

Java

public class FloydWarshall {
    static final int INF = (int) 1e9;

    public static void floydWarshall(int[][] dist) {
        int V = dist.length;

        for (int k = 0; k < V; k++)
            for (int i = 0; i < V; i++)
                for (int j = 0; j < V; j++)
                    if (dist[i][k] != INF && dist[k][j] != INF)
                        dist[i][j] = Math.min(dist[i][j],
                                              dist[i][k] + dist[k][j]);
    }
}

Go

const INF = int(1e9)

func floydWarshall(dist [][]int) {
    V := len(dist)

    for k := 0; k < V; k++ {
        for i := 0; i < V; i++ {
            for j := 0; j < V; j++ {
                if dist[i][k] != INF && dist[k][j] != INF {
                    if dist[i][k]+dist[k][j] < dist[i][j] {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }
    }
}

Path Reconstruction

Thêm ma trận next[i][j] — lưu đỉnh tiếp theo trên shortest path từ i đến j.

C++

void floydWarshallWithPath(vector<vector<int>>& dist,
                           vector<vector<int>>& next) {
    int V = dist.size();
    next.assign(V, vector<int>(V, -1));

    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
            if (dist[i][j] != INF && i != j)
                next[i][j] = j;

    for (int k = 0; k < V; ++k)
        for (int i = 0; i < V; ++i)
            for (int j = 0; j < V; ++j)
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
}

vector<int> getPath(const vector<vector<int>>& next, int u, int v) {
    if (next[u][v] == -1) return {};
    vector<int> path = {u};
    while (u != v) {
        u = next[u][v];
        path.push_back(u);
    }
    return path;
}

Python

def floyd_warshall_with_path(dist: list[list[float]]):
    """Returns (dist, next_matrix) for path reconstruction."""
    V = len(dist)
    INF = float('inf')
    nxt = [[-1] * V for _ in range(V)]

    for i in range(V):
        for j in range(V):
            if dist[i][j] != INF and i != j:
                nxt[i][j] = j

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        nxt[i][j] = nxt[i][k]

    return dist, nxt

def get_path(nxt: list[list[int]], u: int, v: int) -> list[int]:
    if nxt[u][v] == -1:
        return []
    path = [u]
    while u != v:
        u = nxt[u][v]
        if u == -1:
            return []
        path.append(u)
    return path

Java

public static int[][] next;

public static void floydWarshallWithPath(int[][] dist) {
    int V = dist.length;
    next = new int[V][V];
    for (int[] row : next) Arrays.fill(row, -1);

    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            if (dist[i][j] != INF && i != j)
                next[i][j] = j;

    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
}

public static List<Integer> getPath(int u, int v) {
    if (next[u][v] == -1) return Collections.emptyList();
    List<Integer> path = new ArrayList<>();
    path.add(u);
    while (u != v) {
        u = next[u][v];
        path.add(u);
    }
    return path;
}

Go

func floydWarshallWithPath(dist [][]int) [][]int {
    V := len(dist)
    nxt := make([][]int, V)
    for i := range nxt {
        nxt[i] = make([]int, V)
        for j := range nxt[i] {
            nxt[i][j] = -1
            if dist[i][j] != INF && i != j {
                nxt[i][j] = j
            }
        }
    }

    for k := 0; k < V; k++ {
        for i := 0; i < V; i++ {
            for j := 0; j < V; j++ {
                if dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
                }
            }
        }
    }
    return nxt
}

func getPath(nxt [][]int, u, v int) []int {
    if nxt[u][v] == -1 {
        return nil
    }
    path := []int{u}
    for u != v {
        u = nxt[u][v]
        if u == -1 {
            return nil
        }
        path = append(path, u)
    }
    return path
}

Transitive Closure (Bao đóng bắc cầu)

Biến thể Warshall: thay phép min(+) bằng phép OR(AND) để xác định đỉnh nào reachable từ đỉnh nào.

def transitive_closure(adj_matrix: list[list[bool]]) -> list[list[bool]]:
    """
    Warshall's algorithm: reach[i][j] = True nếu tồn tại đường đi i → j.
    Time: O(V³), Space: O(V²)
    """
    V = len(adj_matrix)
    reach = [[adj_matrix[i][j] for j in range(V)] for i in range(V)]
    for i in range(V):
        reach[i][i] = True

    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

    return reach

Thực chiến

Tình huống 1: Network Routing Table

Bối cảnh: Data center có N switch (N ≤ 500) kết nối thành mesh network. Cần tính routing table hoàn chỉnh — mỗi switch biết next hop đến mọi switch khác.

Mục tiêu: Precompute ma trận khoảng cách và next-hop cho toàn bộ topology.

def build_full_routing(
    switches: list[str],
    links: list[tuple[str, str, int]]
) -> dict[str, dict[str, tuple[int, str]]]:
    """
    Xây dựng routing table hoàn chỉnh.
    Returns: {src: {dst: (cost, next_hop)}}
    """
    n = len(switches)
    idx = {s: i for i, s in enumerate(switches)}
    INF = float('inf')

    dist = [[INF] * n for _ in range(n)]
    nxt = [[-1] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for s1, s2, cost in links:
        i, j = idx[s1], idx[s2]
        dist[i][j] = cost
        dist[j][i] = cost
        nxt[i][j] = j
        nxt[j][i] = i

    # Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != INF and dist[k][j] != INF:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        nxt[i][j] = nxt[i][k]

    # Xây routing table
    table = {}
    for i in range(n):
        table[switches[i]] = {}
        for j in range(n):
            if i != j and dist[i][j] != INF:
                table[switches[i]][switches[j]] = (
                    dist[i][j],
                    switches[nxt[i][j]]
                )

    return table

Phân tích: $O(N^3)$ precompute, sau đó mỗi routing lookup là $O(1)$. Phù hợp khi topology thay đổi không thường xuyên (recompute toàn bộ khi có link change). Với N = 500, ${500}^3=125M$ — chạy trong ~1-2 giây trên hardware hiện đại.

Tình huống 2: Kiểm tra reachability trong dependency graph

Bối cảnh: CI/CD system cần biết: "Module A thay đổi → những module nào bị ảnh hưởng?". Dependency graph có ~200 module.

Mục tiêu: Precompute ma trận ảnh hưởng (transitive closure) để trigger rebuild chính xác.

def affected_modules(
    modules: list[str],
    depends_on: dict[str, list[str]]
) -> dict[str, set[str]]:
    """
    Tính transitive closure: module X thay đổi → set các module bị ảnh hưởng.
    depends_on[B] = [A] nghĩa là B phụ thuộc A.
    → Nếu A thay đổi, B cần rebuild.
    """
    n = len(modules)
    idx = {m: i for i, m in enumerate(modules)}

    # Xây ma trận: affects[i][j] = True nếu thay đổi i ảnh hưởng j
    affects = [[False] * n for _ in range(n)]
    for mod, deps in depends_on.items():
        j = idx[mod]
        for dep in deps:
            i = idx[dep]
            affects[i][j] = True  # i thay đổi → j bị ảnh hưởng

    # Transitive closure
    for k in range(n):
        for i in range(n):
            for j in range(n):
                affects[i][j] = affects[i][j] or (affects[i][k] and affects[k][j])

    result = {}
    for i in range(n):
        result[modules[i]] = {modules[j] for j in range(n) if affects[i][j]}

    return result

Phân tích: Precompute $O(N^3)$ — với 200 module, chạy gần như tức thì. Query "module X thay đổi, ai bị ảnh hưởng?" là $O(N)$ lookup. Thay thế cho việc chạy DFS từ mỗi module mỗi khi có change.

Sai lầm điển hình

❌ Sai lầm 1: Sai thứ tự vòng lặp — k không ở ngoài cùng

Vấn đề: Đặt vòng k ở trong thay vì ngoài cùng.

# SAI: k ở vòng trong cùng
for i in range(V):
    for j in range(V):
        for k in range(V):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Tại sao sai: DP yêu cầu khi xét đỉnh trung gian $k$, tất cả shortest path chỉ dùng đỉnh $\{0..k-1\}$ phải đã ổn định. Khi k ở trong cùng, dist[i][k] và dist[k][j] có thể chưa được cập nhật đầy đủ cho tập trung gian hiện tại → kết quả sai.

# ĐÚNG: k ở vòng ngoài cùng
for k in range(V):     # ← K NGOÀI CÙNG
    for i in range(V):
        for j in range(V):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

❌ Sai lầm 2: Quên khởi tạo dist[i][i] = 0

Vấn đề: Để dist[i][i] = INF thay vì 0.

# SAI: dist[i][i] = INF
dist = [[INF] * V for _ in range(V)]
# Thiếu: for i in range(V): dist[i][i] = 0

Tại sao sai: Khoảng cách từ đỉnh đến chính nó là 0. Nếu không khởi tạo, dist[i][k] + dist[k][i] sẽ không tính đúng đường qua trung gian quay về.

# ĐÚNG: khởi tạo đường chéo = 0
dist = [[INF] * V for _ in range(V)]
for i in range(V):
    dist[i][i] = 0

❌ Sai lầm 3: Không kiểm tra INF trước khi cộng

Vấn đề: dist[i][k] + dist[k][j] khi cả hai là INF.

# SAI: INF + INF có thể gây overflow (C++/Java)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Tại sao sai: Trong C++/Java, INT_MAX + INT_MAX overflow thành giá trị âm → relaxation sai → kết quả lỗi. Trong Python, inf + inf = inf nên ít nguy hiểm, nhưng kiểm tra vẫn an toàn hơn.

# ĐÚNG: guard against INF
if dist[i][k] != INF and dist[k][j] != INF:
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

❌ Sai lầm 4: Dùng Floyd-Warshall cho đồ thị sparse với V lớn

Vấn đề: V = 100,000, E = 200,000 (sparse). Dùng Floyd-Warshall.

Tại sao sai: $O(V^3)={10}^{15}$ — chạy hàng ngày. Ma trận $V\times V={10}^{10}$ entry — không vừa memory. Đồ thị sparse nên dùng Dijkstra × V = $O(V\times E\log V)\approx {10}^{12}$ — vẫn chậm nhưng khả thi hơn nhiều.

ĐÚNG: Floyd-Warshall chỉ hiệu quả khi V nhỏ (thường ≤ 1000) 
       hoặc đồ thị dense (E ≈ V²).
       Sparse + V lớn → Dijkstra/Bellman-Ford chạy V lần.

Under the Hood

Hiệu năng

Aspect	Complexity	Ghi chú
Time	$O(V^3)$	Ba vòng lặp lồng nhau — không thể giảm
Space	$O(V^2)$	Ma trận khoảng cách + ma trận next (nếu truy vết)
Path reconstruction	$O(V)$	Duyệt theo next[] pointers
Phát hiện chu trình âm	$O(V)$	Kiểm tra dist[i][i] < 0

Nội bộ triển khai

Cache performance: Floyd-Warshall có access pattern tốt cho CPU cache khi V nhỏ (ma trận nằm gọn trong L2/L3 cache). Với V lớn, ma trận tràn cache → cache miss liên tục → chậm hơn lý thuyết.

Parallelization: Vòng i và j trong mỗi iteration k hoàn toàn độc lập → có thể parallelized. Trên GPU hoặc multi-core CPU, Floyd-Warshall scale tốt. Đây là lý do nó được dùng trong high-performance network simulation.

Phát hiện chu trình âm: Sau khi chạy Floyd-Warshall, nếu dist[i][i] < 0 cho bất kỳ i nào → đỉnh i nằm trên chu trình âm. Mọi cặp (u, v) mà dist[u][i] < INF và dist[i][v] < INF đều bị ảnh hưởng (shortest path = $-\mathrm{\infty }$).

Trade-offs: Floyd-Warshall vs chạy Dijkstra V lần

Tiêu chí	Floyd-Warshall	Dijkstra × V
Time	$O(V^3)$	$O(V(V+E)\log V)$
Dense graph ($E\approx V^2$)	$O(V^3)$ ✅	$O(V^3\log V)$
Sparse graph ($E\approx V$)	$O(V^3)$	$O(V^2\log V)$ ✅
Trọng số âm	✅	❌ (cần Bellman-Ford × V)
Cài đặt	Rất đơn giản	Phức tạp hơn (heap)
Memory	$O(V^2)$ ma trận	$O(V+E)$ mỗi lần chạy

Quy tắc chọn: Dense graph + V nhỏ (≤ 1000) + cần all-pairs → Floyd-Warshall. Sparse graph + V lớn → Dijkstra × V. Trọng số âm + sparse → Johnson's algorithm (Bellman-Ford reweight + Dijkstra × V).

Checklist ghi nhớ

✅ Checklist triển khai

Trước khi code

• [ ] Xác nhận cần all-pairs (nếu chỉ single-source → dùng Dijkstra/Bellman-Ford)
• [ ] Kiểm tra V ≤ 1000 (Floyd-Warshall yêu cầu $O(V^2)$ memory và $O(V^3)$ time)
• [ ] Dense hay sparse? Sparse + V lớn → Dijkstra × V hiệu quả hơn

Khi code Floyd-Warshall

• [ ] Vòng k ngoài cùng — sai thứ tự = sai kết quả
• [ ] Khởi tạo dist[i][i] = 0 cho mọi i
• [ ] Guard dist[i][k] != INF && dist[k][j] != INF trước khi cộng
• [ ] Khởi tạo next[i][j] = j nếu cần path reconstruction

Sau khi chạy

• [ ] Kiểm tra dist[i][i] < 0 → phát hiện chu trình âm
• [ ] Xác định đỉnh bị ảnh hưởng bởi chu trình âm (nếu cần)
• [ ] Path reconstruction: duyệt next[i][j] cho đến khi đến đích

Bài tập luyện tập

Bài 1: All-Pairs Shortest Path cơ bản — Foundation

Đề bài: Cho đồ thị có hướng V đỉnh, E cạnh với ma trận kề. Tính ma trận khoảng cách ngắn nhất giữa mọi cặp đỉnh.

Input (ma trận kề):
    0   3   ∞   7
    8   0   2   ∞
    5   ∞   0   1
    2   ∞   ∞   0

Output:
    0   3   5   6
    5   0   2   3
    3   6   0   1
    2   5   7   0

🧠 Quiz

Câu hỏi: Tại sao vòng k phải ở ngoài cùng trong Floyd-Warshall?

• [ ] A. Vì vòng k ở trong sẽ chạy chậm hơn
• [ ] B. Vì compiler không tối ưu được vòng k ở trong
• [x] C. Vì DP yêu cầu tất cả dist[i][j] dùng tập trung gian {0..k-1} phải ổn định trước khi xét k
• [ ] D. Vì k ở trong sẽ gây tràn bộ nhớ Giải thích: Floyd-Warshall là DP theo tập đỉnh trung gian. dp[k][i][j] phụ thuộc dp[k-1][i][k] và dp[k-1][k][j]. Khi k ở ngoài cùng, mỗi iteration k sử dụng kết quả đã ổn định từ iteration k-1. Đặt k ở vòng trong phá vỡ bất biến này.

💡 Gợi ý

• Khởi tạo ma trận dist từ adjacency matrix
• Đặt dist[i][i] = 0
• Ba vòng for: k → i → j

✅ Lời giải

def solve(matrix: list[list[float]]) -> list[list[float]]:
    V = len(matrix)
    INF = float('inf')
    dist = [row[:] for row in matrix]  # Copy

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

Phân tích: Time $O(V^3)$, Space $O(V^2)$. Cài đặt đơn giản nhất trong tất cả thuật toán shortest path.

Bài 2: Phát hiện chu trình âm và truy vết đường đi — Intermediate

Đề bài: Chạy Floyd-Warshall trên đồ thị có trọng số (có thể âm). In ma trận khoảng cách. Nếu có chu trình âm, in ra các đỉnh nằm trên chu trình. Truy vết và in đường đi ngắn nhất giữa hai đỉnh cho trước.

💡 Gợi ý

• Sau Floyd-Warshall, kiểm tra dist[i][i] < 0 → đỉnh trên chu trình âm
• Dùng ma trận next[] để truy vết
• Đường đi bị ảnh hưởng bởi chu trình âm → dist = -∞, không truy vết được

✅ Lời giải

def solve_full(matrix: list[list[float]], src: int, dst: int):
    V = len(matrix)
    INF = float('inf')
    dist = [row[:] for row in matrix]
    nxt = [[-1] * V for _ in range(V)]

    for i in range(V):
        for j in range(V):
            if dist[i][j] != INF and i != j:
                nxt[i][j] = j

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        nxt[i][j] = nxt[i][k]

    # Phát hiện chu trình âm
    neg_cycle_nodes = [i for i in range(V) if dist[i][i] < 0]

    # Truy vết đường đi src → dst
    path = []
    if nxt[src][dst] != -1:
        cur = src
        visited = set()
        while cur != dst:
            if cur in visited:
                path = []  # Vòng lặp
                break
            visited.add(cur)
            path.append(cur)
            cur = nxt[cur][dst]
        if path:
            path.append(dst)

    return dist, neg_cycle_nodes, path

Phân tích: Time $O(V^3)$, Space $O(V^2)$. Kiểm tra vòng lặp khi truy vết phòng trường hợp đường đi qua chu trình âm.

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← Bellman-Ford — Single-source shortest path với trọng số âm
• → MST — Prim & Kruskal — Cây khung nhỏ nhất
• Dijkstra — Single-source shortest path, so sánh hiệu năng
• Dynamic Programming cơ bản — Nền tảng DP mà Floyd-Warshall dựa trên

Từ khóa glossary: Floyd-Warshall, all-pairs shortest path, transitive closure, dynamic programming, routing table, adjacency matrix

Tìm kiếm liên quan: Floyd-Warshall algorithm, all-pairs shortest path, bao đóng bắc cầu, thuật toán đường đi ngắn nhất mọi cặp