Floyd Warshall Algorithm

Trung bìnhĐường đi ngắn nhất Quy hoạch động

+10

Cho một đồ thị có hướng gồm n nút, được đánh số từ 0 đến n-1, biểu diễn bằng ma trận n × n: matrix[i][j] là trọng số của cạnh từ nút i đến nút j, hoặc là -1 nếu không có cạnh, còn matrix[i][i] là 0. Độ dài của một đường đi bằng tổng trọng số các cạnh trên đường đi đó.

Trả về ma trận n × n, trong đó phần tử [i][j] là độ dài của đường đi ngắn nhất từ nút i đến nút j, hoặc là -1 nếu không thể đi từ nút i đến nút j.

Hàm

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: trọng số của các cạnh: matrix[i][j] là trọng số của cạnh từ i đến j, hoặc -1 nếu không có cạnh
Trả vềinteger-2d-array: khoảng cách ngắn nhất cho mỗi cặp nút, -1 nếu không có đường đi

Ràng buộc

1 ≤ n ≤ 100, trong đó n = matrix.length = matrix[i].length
matrix[i][i] = 0
Với i ≠ j, matrix[i][j] bằng -1 (không có cạnh) hoặc 0 ≤ matrix[i][j] ≤ 1000.
Các cạnh chỉ có một chiều: matrix[i][j] và matrix[j][i] độc lập với nhau.

Ví dụ

Đầu vào: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Đầu ra: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Giải thích: Thông qua nút 1, nút 0 đến nút 2 với chi phí 6 thay vì 11, và đến nút 3 với chi phí 9. Nút 1 đến nút 0 thông qua nút 2 với chi phí 3. Không có đường đi nào xuất phát từ nút 3, nên hàng của nút này có giá trị -1 ở ngoài đường chéo.

Đầu vào: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Đầu ra: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Giải thích: Cạnh từ 2 đến 1 có trọng số 0, nên 0 → 2 → 1 có chi phí 1, thấp hơn đường đi trực tiếp có chi phí 6. Không có cạnh nào đi ra từ nút 1 hoặc đi vào nút 0, nên các cặp đó vẫn giữ giá trị -1.

Câu hỏi mở rộng

Sau khi bạn dựng bảng, một cạnh sẽ có chi phí thấp hơn. Bạn có thể cập nhật mọi khoảng cách trong O(n²) thay vì chạy lại các vòng lặp O(n³) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Bạn cần tìm đường đi ngắn nhất cho mọi cặp nút. Floyd-Warshall tìm tất cả n² đáp án bằng một vòng lặp lồng ba lần. Mỗi lượt cho phép các tuyến đường đi qua thêm một nút và cần một phép so sánh cho mỗi cặp: tuyến đường tốt nhất đến lúc đó so với tuyến đường đi qua nút mới.

Mở rộng mỗi tuyến đường thêm một cạnh cho đến khi không còn gì thay đổi

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Bắt đầu từ ma trận (matrix), rồi ở mỗi lượt (pass), nối thêm một cạnh (edge) vào mọi tuyến đường (route): một tuyến đường từ i đến m cộng với cạnh m → j tạo thành tuyến đường từ i đến j, và giữ lại tuyến đường đó nếu nó ngắn hơn. Lặp lại cho đến khi một lượt không làm thay đổi gì.

Sau p lượt, ta tìm được mọi tuyến đường ngắn nhất có tối đa p+1 cạnh. Không có trọng số nào âm, nên một tuyến đường ngắn nhất nào đó không có vòng lặp và có tối đa n-1 cạnh; các lượt sẽ dừng khi mọi khoảng cách đã ổn định. Một lượt cần n³ = 10^6 bước với 100 nút, còn một chuỗi dài các tuyến đường ngắn nhất cần tối đa n lượt: O(n⁴), tối đa 10^8 bước.

Thuật toán

Sao chép matrix vào dist.
Với mỗi i, m và j: nếu cả dist[i][m] và matrix[m][j] đều tồn tại, hãy tính tổng của chúng.
Nếu dist[i][j] là -1 hoặc lớn hơn tổng đó, hãy lưu tổng đó và ghi nhớ rằng lượt duyệt đã thay đổi dữ liệu.
Lặp lại lượt duyệt cho đến khi không còn gì thay đổi, rồi trả về dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: cho phép thêm một điểm dừng sau mỗi lượt

Ý tưởng

Giới hạn những nút mà một tuyến đường có thể dừng tại giữa điểm đầu và điểm cuối. Bảng khởi đầu là ma trận gồm các tuyến đường không có điểm dừng. Sau vòng k, dist[i][j] là tuyến đường ngắn nhất có tất cả điểm dừng nằm trong các nút từ 0 đến k, và vòng cuối cùng cho kết quả.

Trong vòng k, tuyến đường tốt nhất có thể dừng tại k hoặc bỏ qua k, khi đó bảng đã lưu sẵn tuyến đường này, hoặc đi qua k một lần, vì không có trọng số nào âm. Hai nửa tuyến đường chỉ dừng tại các nút từ 0 đến k-1, nên chúng là dist[i][k] và dist[k][j].

Trong ví dụ đầu tiên, vòng 1 thay tuyến đường trực tiếp dài 11 từ nút 0 đến nút 2 bằng tuyến đường dài 6. Vòng 2 cho tuyến đường từ nút 0 đến nút 3 dài 6 + 3 = 9, với điểm dừng tại nút 1 nằm bên trong đoạn đường dài 6.

Chỉ cần một bảng: hàng k và cột k không thay đổi trong vòng k, vì dist[k][k] bằng 0.

Thuật toán

Sao chép matrix vào dist; -1 có nghĩa là chưa tìm thấy đường đi.
Với k từ 0 đến n-1, và với mọi i và j: bỏ qua cặp này nếu dist[i][k] hoặc dist[k][j] là -1.
Nếu không, hãy tính via = dist[i][k] + dist[k][j].
Nếu dist[i][j] là -1 hoặc lớn hơn via, hãy đặt nó bằng via.
Trả về dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Lỗi thường gặp và trường hợp biên

Thêm -1 như thể đó là một trọng số: -1 + 5 = 4 trông giống một tuyến đường. Trước tiên, hãy kiểm tra cả hai phần và xem -1 trong dist[i][j] là giá trị kém hơn bất kỳ tuyến đường nào.
Đặt vòng lặp qua k bên trong. Các tuyến đường đi qua những điểm dừng từ 0 đến k-1 phải được hoàn tất trước khi đưa nút k vào.
Dùng số nguyên lớn nhất làm vô cực: cộng hai số sẽ gây tràn số nguyên 32 bit, tạo ra khoảng cách âm. Khoảng cách thực tối đa là 99 × 1000 = 99,000, vì vậy 10^9 là an toàn, do 2 × 10^9 nhỏ hơn 2^31-1.
Cho rằng các cạnh đi theo cả hai hướng. Trong ví dụ thứ hai, nút 0 đến được nút 1, nhưng từ nút 1 không đến được nút nào.
Chạy tìm kiếm theo chiều rộng, vốn bỏ qua trọng số: trong ví dụ đầu tiên, thuật toán trả về 11 cho đường đi từ nút 0 đến nút 2, thay vì 6.

Câu hỏi thường gặp3

Độ phức tạp thời gian của thuật toán Floyd Warshall là bao nhiêu?

Thời gian O(n³) với n nút: ba vòng lặp lồng nhau qua các nút, mỗi bước có một phép cộng và một phép so sánh, 10^6 bước với 100 nút. Bộ nhớ là O(n²) cho bảng khoảng cách, có thể cập nhật trực tiếp.

Floyd Warshall có hoạt động với trọng số cạnh âm không?

Đúng, miễn là không có chu trình âm, tức là vòng lặp có tổng trọng số nhỏ hơn 0. Khi có chu trình âm, đường đi ngắn nhất không được xác định, và bảng cho thấy điều đó: một số dist[i][i] có giá trị nhỏ hơn 0.

Khi nào bạn nên dùng Floyd Warshall thay vì thuật toán Dijkstra?

Dùng Floyd-Warshall cho mọi cặp nút trong đồ thị dày có tối đa vài trăm nút. Chạy Dijkstra từ mọi nút tốn O(n³) khi dùng mảng và O(n · E log n) khi dùng heap, phù hợp hơn với đồ thị thưa lớn. Floyd-Warshall không cần heap và chấp nhận cạnh âm, còn Dijkstra thì không.

def shortestDistances(matrix):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Đầu ra mong đợi

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]