Thuật toán Floyd-Warshall là gì: cách hoạt động, code và độ phức tạp

Floyd-Warshall giải bài toán gì

Đôi khi bạn cần khoảng cách giữa mọi cặp địa điểm chứ không chỉ từ một điểm xuất phát: bảng thời gian di chuyển giữa tất cả các thành phố, độ trễ giữa mọi cặp máy chủ, hoặc khả năng tiếp cận đầy đủ của một đồ thị phụ thuộc. Floyd-Warshall giải bài toán đường đi ngắn nhất mọi cặp này bằng một thuật toán quy hoạch động rất ngắn.

Thuật toán được Robert Floyd công bố năm 1962 (“Algorithm 97: Shortest path”), dựa trên thuật toán bao đóng bắc cầu của Stephen Warshall cũng năm 1962.

Ý tưởng bằng lời đơn giản

Đánh số các nút từ 0 đến V − 1. Sau khi xử lý nút k, dist[i][j] là đường đi ngắn nhất từ i đến j chỉ dùng các nút từ 0 đến k làm điểm dừng trung gian. Cho phép thêm một nút trung gian k cho hai lựa chọn: đường tốt nhất cũ không đi qua k, hoặc đường i → k → j gồm hai đường tốt nhất mà mỗi đường chỉ dùng các nút trước k.

1. Điền ma trận: 0 trên đường chéo, trọng số cạnh ở những nơi có cạnh, vô cùng ở nơi còn lại.
2. Với k từ 0 đến V − 1, với mọi cặp (i, j): nếu dist[i][k] + dist[k][j] < dist[i][j] thì cập nhật.
3. Sau k cuối cùng, ma trận chứa mọi khoảng cách ngắn nhất. Giá trị âm trên đường chéo nghĩa là có chu trình âm.

Thứ tự các vòng lặp rất quan trọng: k phải là vòng lặp ngoài cùng.

Ví dụ từng bước

Đồ thị có hướng với 4 nút và các cạnh 0→1 (3), 0→3 (7), 1→0 (8), 1→2 (2), 2→0 (5), 2→3 (1), 3→0 (2). Ma trận ban đầu (hàng = nút đi, cột = nút đến):

1. k = 0: các đường có thể đi qua nút 0. 1→3 thành 8 + 7 = 15, 2→1 thành 5 + 3 = 8 và 3→1 thành 2 + 3 = 5.
2. k = 1: qua nút 1. 0→2 thành 3 + 2 = 5 và 3→2 thành 5 + 2 = 7.
3. k = 2: qua nút 2. 0→3 cải thiện từ 7 xuống 5 + 1 = 6, 1→3 từ 15 xuống 2 + 1 = 3, và 1→0 từ 8 xuống 2 + 5 = 7.
4. k = 3: qua nút 3. 1→0 cải thiện từ 7 xuống 3 + 2 = 5, 2→0 từ 5 xuống 1 + 2 = 3, và 2→1 từ 8 xuống 1 + 5 = 6.

Các hàng của ma trận cuối: 0 → [0, 3, 5, 6], 1 → [5, 0, 2, 3], 2 → [3, 6, 0, 1], 3 → [2, 5, 7, 0].

Cài đặt bằng Python

INF = float("inf")
def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            for j in range(n):
                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
edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2),
         (2, 0, 5), (2, 3, 1), (3, 0, 2)]
dist, nxt = floyd_warshall(4, edges)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

Ma trận nxt lưu bước đầu tiên trên đường tốt nhất từ i đến j, đủ để dựng lại bất kỳ đường đi nào:

def path(nxt, i, j):
    if nxt[i][j] is None:
        return []                         # no path
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route
print(path(nxt, 1, 0))  # [1, 2, 3, 0]

Nếu có nhiều nút và muốn nhanh hơn trong Python, cùng ba vòng lặp đó có thể viết bằng NumPy với một phép cập nhật vector hóa cho mỗi k: d = np.minimum(d, d[:, k, None] + d[None, k, :]).

Độ phức tạp thời gian và không gian

Với đồ thị thưa có trọng số không âm, chạy Dijkstra từ mọi nút tốn O(V × (V + E) log V), nhanh hơn O(V³) khi E nhỏ hơn nhiều so với V².

Biến thể và lỗi thường gặp

• Chu trình âm: sau các vòng lặp, nếu dist[i][i] < 0 với một i nào đó thì nút i nằm trên một chu trình âm và đường đi ngắn nhất qua nó không xác định.
• Bao đóng bắc cầu (Warshall): dùng giá trị boolean và thay min/cộng bằng or/and: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]).
• Đường đi minimax và maximin: thay + bằng max (hoặc min) để tìm, chẳng hạn, đường đi mà cạnh lớn nhất của nó nhỏ nhất có thể.
• Chỉ dùng một số hữu hạn lớn thay cho vô cùng nếu chắc chắn tổng của hai số như vậy không tràn; trong Python, float("inf") là lựa chọn an toàn.
• Khởi tạo đường chéo bằng 0, và khi có các cạnh song song thì giữ trọng số nhỏ nhất.

Khi nào dùng và ứng dụng thực tế

• Tính trước bảng khoảng cách giữa mọi trạm, kho hoặc thành phố để tra cứu sau.
• Phân tích đồ thị như độ trung tâm gần (closeness centrality) hoặc đường kính của một mạng nhỏ.
• Bài phỏng vấn: tìm thành phố có ít láng giềng nhất trong ngưỡng khoảng cách, evaluate division (tỷ lệ là tích trên đường đi), điều kiện tiên quyết môn học dưới dạng bao đóng bắc cầu.