Thuật toán Floyd–Warshall là gì? Giải thích dễ hiểu kèm demo

Bài viết này giới thiệu ý tưởng của Floyd–Warshall, cách hoạt động và kèm một demo trực quan bằng JavaScript để bạn thấy từng bước cập nhật ma trận khoảng cách.

Bài toán Floyd–Warshall giải quyết

Bài toán đặt ra như sau:

• Cho một đồ thị có trọng số (có thể có cạnh âm, nhưng không có chu trình âm).
• Mỗi cạnh có trọng số thể hiện chi phí hoặc độ dài.
• Cần tìm khoảng cách ngắn nhất giữa mọi cặp đỉnh (i, j).

Kết quả là một ma trận khoảng cách, trong đó mỗi ô dist[i][j] là tổng trọng số nhỏ nhất để đi từ đỉnh i đến j.

Ý tưởng chính của thuật toán Floyd–Warshall

Floyd–Warshall sử dụng cách tư duy “dần dần cho phép thêm đỉnh trung gian”:

1. Ban đầu, chỉ cho phép đường đi trực tiếp (hoặc không đi nếu không có cạnh).
2. Lần lượt cho phép mỗi đỉnh k trở thành đỉnh trung gian trên đường đi giữa mọi cặp (i, j).
3. Với mỗi k, kiểm tra xem đi từ i đến j thông qua k có ngắn hơn đường đi hiện tại không:

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

4. Sau khi thử tất cả đỉnh k, ma trận khoảng cách thu được là khoảng cách ngắn nhất giữa mọi cặp đỉnh.

Điểm hay của Floyd–Warshall là code rất gọn (ba vòng lặp lồng nhau), nhưng đổi lại độ phức tạp là O(n³), phù hợp cho đồ thị vừa và nhỏ.

Đồ thị sử dụng trong demo

Để minh họa, ta dùng một đồ thị nhỏ gồm 4 đỉnh A, B, C, D với các cạnh có hướng và trọng số như sau:

A → B (3), A → D (7)
B → A (8), B → C (2)
C → A (5), C → D (1)
D → A (2)

Không có cạnh nào mang trọng số âm và không có chu trình âm. Tuy nhiên, thuật toán Floyd–Warshall vẫn có thể xử lý được cạnh âm (nếu có) miễn là không tồn tại chu trình âm.

Demo Floyd–Warshall bằng JavaScript

Demo dưới đây thực hiện:

• Cho phép chọn đỉnh bắt đầu và kết thúc.
• Chạy thuật toán Floyd–Warshall và hiển thị ma trận khoảng cách sau mỗi bước với đỉnh trung gian k.
• Sau khi kết thúc, hiển thị đường đi ngắn nhất và tổng trọng số giữa hai đỉnh đã chọn.

Phân tích đoạn code Floyd–Warshall

1. Khởi tạo ma trận khoảng cách và ma trận next

for (var i = 0; i < n; i++) {
    dist[i][i] = 0;
    next[i][i] = i;
}
edges.forEach(function(e) {
    var i = indexOf[e.from];
    var j = indexOf[e.to];
    dist[i][j] = e.w;
    next[i][j] = j;
});

Mỗi đỉnh có khoảng cách đến chính nó là 0. Nếu có cạnh trực tiếp từ i đến j, ta gán trọng số và ghi nhận “bước tiếp theo” từ i khi đi tới j là j.

2. Ba vòng lặp chính của thuật toán

for (var k = 0; k < n; k++) {
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            if (dist[i][k] === INF || dist[k][j] === INF) continue;
            var alt = dist[i][k] + dist[k][j];
            if (alt < dist[i][j]) {
                dist[i][j] = alt;
                next[i][j] = next[i][k];
            }
        }
    }
}

Mỗi vòng lặp ngoài cùng chọn một đỉnh k làm đỉnh trung gian. Hai vòng lặp còn lại duyệt qua mọi cặp (i, j) và cập nhật nếu đi qua k giúp đường đi i → j ngắn hơn.

3. Xây dựng lại đường đi từ ma trận next

function buildPath(nextMatrix, startNode, endNode, distMatrix) {
    var i = indexOf[startNode];
    var j = indexOf[endNode];

    if (nextMatrix[i][j] === null) {
        return null;
    }

    var path = [startNode];
    var current = i;
    while (current !== j) {
        current = nextMatrix[current][j];
        path.push(nodes[current]);
    }

    return {
        path: path,
        distance: distMatrix[i][j]
    };
}

Ma trận next cho biết nếu đang ở i và muốn đến j thì bước tiếp theo phải đi đến đỉnh nào. Dựa vào đó, ta có thể lần theo để dựng lại toàn bộ đường đi, không chỉ biết mỗi tổng trọng số.

Khi nào nên dùng Floyd–Warshall?

• Khi cần khoảng cách ngắn nhất giữa mọi cặp đỉnh.
• Khi số đỉnh không quá lớn (do độ phức tạp O(n³)).
• Khi đồ thị có thể có cạnh âm nhưng không có chu trình âm.
• Khi cần truy vấn đường đi nhiều lần sau khi tiền xử lý một lần.

Kết luận

Floyd–Warshall là một thuật toán mạnh mẽ và súc tích cho bài toán đường đi ngắn nhất giữa mọi cặp đỉnh. Mặc dù có độ phức tạp O(n³), nhưng với các đồ thị kích thước vừa, thuật toán này mang lại một “bản đồ đầy đủ” về khoảng cách và đường đi giữa tất cả các nút.

Thông qua demo JavaScript ở trên, bạn có thể quan sát rõ cách ma trận khoảng cách được cập nhật sau từng bước, khi lần lượt cho phép các đỉnh đóng vai trò trung gian.

Khi kết hợp hiểu biết về BFS, Dijkstra, Bellman–Ford và Floyd–Warshall, bạn đã có một bộ công cụ vững chắc để xử lý phần lớn các bài toán đường đi trong lĩnh vực thuật toán và lập trình ứng dụng.