Floyd–Warshall: đường ngắn nhất giữa mọi cặp đỉnh

Khi đề hỏi rất nhiều cặp nguồn–đích

Giả sử có một bản đồ thành phố nhỏ nhưng rất nhiều câu hỏi: từ a tới b rẻ nhất bao nhiêu? Nếu mỗi lần hỏi lại chạy một thuật toán từ đầu, ta tính đi tính lại cùng thông tin. Floyd–Warshall tiền xử lý bảng d[i][j] cho mọi cặp, sau đó mỗi truy vấn khoảng cách chỉ đọc một ô.

Đổi lại, bảng có n² ô và quá trình xử lý có n³ bộ ba chỉ số. Đây là lựa chọn tự nhiên khi số đỉnh đủ nhỏ và cần thông tin mọi cặp. Nó không phải cách mặc định cho một đồ thị hàng trăm nghìn đỉnh chỉ hỏi một đường đi.

Khởi tạo ma trận đúng từ đầu

Đặt d[i][i]=0 vì đường không đi cạnh nào có chi phí 0. Với cạnh i → j trọng số w, đặt d[i][j] là giá trị nhỏ hơn giữa ô hiện tại và w. Phép lấy min quan trọng khi có nhiều cạnh cùng hai đầu; cạnh nhập sau không nhất thiết tốt hơn cạnh trước.

Cặp chưa biết đường đi mang INF. Nếu đồ thị vô hướng, cập nhật cả d[u][v] và d[v][u]. Code mẫu của bài chỉ thêm chiều nhập vào. Với cạnh tự nối có trọng số âm, lấy min với 0 sẽ giữ được giá trị âm để phần kiểm chu trình phát hiện; không được ghi đè đường chéo thành 0 sau khi đã đọc hết cạnh rồi xóa mất dấu hiệu này.

Trong Python, tạo từng hàng độc lập bằng biểu thức lặp, không nhân cùng một danh sách hàng n lần. Nếu các hàng cùng trỏ vào một đối tượng, thay một ô ở hàng này có thể làm những hàng khác đổi theo, khiến toàn bộ ma trận sai dù công thức thuật toán vẫn đúng.

Ý nghĩa của đỉnh trung gian k

Sau khi xử lý k, d[i][j] là khoảng cách tốt nhất khi những đỉnh nằm giữa hai đầu đường đi chỉ được lấy trong tập 0 tới k. Có hai khả năng: đường tốt nhất không dùng k, hoặc đi từ i tới k rồi từ k tới j. Vì thế ta thử giá trị d[i][k]+d[k][j] để cải thiện d[i][j].

Ở đây k không phải nguồn đang hỏi, cũng không phải số cạnh được phép đi. Nó là đỉnh mới được cho phép làm trung gian. Hiểu đúng trạng thái này giải thích vì sao vòng k cần ở ngoài hai vòng i và j trong bản chuẩn.

Trong trường hợp không có chu trình âm, d[k][k]=0 nên các khoảng cách đi tới hoặc đi ra k không bị giảm bất thường trong pha k. Vì vậy ta có thể cập nhật tại chỗ trên cùng ma trận. Nếu có chu trình âm, ta chỉ dùng quá trình đó để phát hiện và báo lỗi theo quy ước code, không gọi các ô bị giảm mãi là khoảng cách ngắn nhất hữu hạn.

Chạy tay vài ô quan trọng

Các cạnh là 0 → 1 giá 4, 0 → 2 giá 1, 2 → 1 giá 2, 1 → 3 giá 1, 2 → 3 giá 5, 3 → 4 giá 3. Ban đầu chỉ có các cạnh trực tiếp và đường chéo. Theo thứ tự k từ 0 tới 4, những cải thiện tiêu biểu là:

Ma trận cuối cùng dưới đây giúp tự đối chiếu đủ 25 ô, thay vì chỉ kiểm một cặp vô tình đúng.

Ví dụ không có đường đi từ 4 về 0 vì cạnh có hướng. Ma trận không đối xứng là điều bình thường; tự ép hai ô đối xứng bằng nhau sẽ giải nhầm sang đồ thị vô hướng.

Code C++ và Python

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
const long long INF=1LL<<60;
pair<bool,vector<long long>> shortest(int n,const vector<tuple<int,int,long long>>&edges,int){
    vector<vector<long long>>d(n,vector<long long>(n,INF));for(int i=0;i<n;++i)d[i][i]=0;
    for(auto[u,v,w]:edges)d[u][v]=min(d[u][v],w);
    for(int k=0;k<n;++k)for(int i=0;i<n;++i)if(d[i][k]!=INF)
        for(int j=0;j<n;++j)if(d[k][j]!=INF)d[i][j]=min(d[i][j],max(-INF,d[i][k]+d[k][j]));
    for(int i=0;i<n;++i)if(d[i][i]<0)return {true,{}};
    vector<long long>out;for(auto&row:d)out.insert(out.end(),row.begin(),row.end());return {false,out};
}

int main(){int n=5,m,s=0;vector<tuple<int,int,long long>>edges={{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5},{3,4,3}};
if(cin>>n>>m){edges.resize(m);for(auto&[u,v,w]:edges)cin>>u>>v>>w;}
auto[bad,out]=shortest(n,edges,s);if(bad){cout<<"NEGATIVE_CYCLE\n";return 0;}for(auto x:out){if(x==INF)cout<<"INF ";else cout<<x<<' ';}cout<<'\n';}

INF=1<<60
def solve(n,edges,s=0):
    d=[[INF]*n for _ in range(n)]
    for i in range(n):d[i][i]=0
    for u,v,w in edges:d[u][v]=min(d[u][v],w)
    for k in range(n):
        for i in range(n):
            if d[i][k]==INF:continue
            for j in range(n):
                if d[k][j]!=INF:d[i][j]=min(d[i][j],max(-INF,d[i][k]+d[k][j]))
    return any(d[i][i]<0 for i in range(n)),[x for row in d for x in row]

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    if d:
        n,m=d[:2];off=2;s=0 if off==2 else d[2]
        width=3;edges=[tuple(d[i:i+width]) for i in range(off,off+width*m,width)]
    else:
        n,s,edges=5,0,[(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
    bad,out=solve(n,edges,s)
    print('NEGATIVE_CYCLE' if bad else ' '.join('INF' if x==INF else str(x) for x in out))

Chạy không nhập dữ liệu cho đúng ma trận trên, nhưng tệp in phẳng lần lượt từng hàng trên một dòng để dễ so kết quả. Với dữ liệu riêng, nhập n, m rồi m bộ u v w. Không có tham số nguồn s vì thuật toán tính mọi nguồn. Cho phép n bằng 0, còn mọi đầu cạnh phải nằm trong [0,n).

Hai điều kiện d[i][k] khác INF và d[k][j] khác INF bảo đảm chỉ nối hai đoạn đường thật sự tồn tại. Đặc biệt với trọng số âm, cộng INF với một số âm rồi cập nhật có thể tạo đường giả. Không thể dùng một con số rất lớn để thay luôn việc kiểm khả năng đi tới.

INF trong ví dụ bằng 2 mũ 60; các trọng số và khoảng cách hữu hạn cần dùng phải có trị tuyệt đối nhỏ hơn INF. Khi xét dữ liệu có chu trình âm, code chặn giá trị âm ở −INF để các lần cộng không vượt miền long long. Các toán hạng hữu hạn luôn được giữ trong khoảng [−INF,INF), nên tổng hai toán hạng còn vừa kiểu số này. Phép chặn chỉ phục vụ phát hiện chu trình an toàn; nó không biến âm vô hạn thành một khoảng cách thật để xuất.

Chu trình âm: kiểm toàn đồ thị hay từng cặp?

Sau khi tính, nếu một ô d[k][k] âm, có một đường vòng từ k về k mang tổng âm. Code trả NEGATIVE_CYCLE nếu thấy bất kỳ đường chéo âm nào, kể cả khi chu trình nằm trong một thành phần tách biệt với những đỉnh khác. Đây là phạm vi toàn đồ thị vì bài đang xử lý mọi cặp.

Không phải mọi cặp i,j đều mất đáp án hữu hạn chỉ vì ở đâu đó có chu trình âm. Cặp bị ảnh hưởng khi i đi được tới một đỉnh k thuộc chu trình âm và từ k đi tiếp được tới j. Nếu đề yêu cầu phân loại từng truy vấn, cần bổ sung kiểm khả năng đi tới và đánh dấu các cặp liên quan. Tệp minh họa chỉ báo một cờ toàn cục, chưa xuất bảng phân loại đó.

So với Bellman–Ford một nguồn, khác biệt này rất quan trọng: chu trình nằm ngoài vùng đi tới của nguồn không kích hoạt cờ trong bản một nguồn, nhưng vẫn được Floyd–Warshall nhận ra trên đường chéo của thành phần riêng ấy.

Chọn thuật toán theo kích thước và nhu cầu

Ba vòng lặp có n³ bộ chỉ số: n=200 cho 8.000.000, n=500 cho 125.000.000, n=1.000 cho 1.000.000.000. Đây là số bộ xét lý thuyết, không phải số giây chạy hoặc bảo đảm vượt qua hệ thống chấm. Việc bỏ qua các đoạn INF có thể giảm một số phép cộng, nhưng không đổi cận tổng quát O(n³).

Ma trận khoảng cách dùng O(n²) ô. Với C++ và kiểu 8 byte, riêng dữ liệu n=1.000 đã cần 8.000.000 byte, chưa kể cấu trúc chứa và phần còn lại của chương trình. Python có chi phí đối tượng và danh sách khác, nên không thể lấy con số 8 byte mỗi ô áp trực tiếp cho toàn bộ chương trình Python.

Các bài tự kiểm trước khi nộp

Hãy thử hai đỉnh không cạnh: chỉ đường chéo bằng 0. Thử hai cạnh 0 → 1 có giá 5 và 2: đáp án phải là 2 dù nhập theo thứ tự nào. Thử chuỗi có cạnh âm nhưng không có vòng: kết quả vẫn hữu hạn. Cuối cùng, thêm một chu trình âm nằm riêng để kiểm cờ toàn cục.

Khi tự kiểm tra trên đồ thị nhỏ, bạn có thể chạy Bellman-Ford xuất phát từ từng đỉnh rồi so sánh với ma trận của Floyd–Warshall. Hãy thử thêm dữ liệu có nhiều cạnh âm để kiểm tra điều kiện chặn INF chống tràn số, cùng các cạnh song song trùng cặp đỉnh để chắc chắn bước khởi tạo ma trận đã giữ lại trọng số nhỏ nhất.

Luyện ngay trên Big-O Coding

Bài mọi cặp luyện công thức chuẩn. Bài mở dần thành phố trung gian đi sâu vào ý nghĩa của pha k: đỉnh nào được phép làm trung gian, cặp đầu–cuối nào đang được tính tổng. Hãy tách rõ hai tập đó trước khi viết vòng lặp.

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

Nguồn tham khảo

• CP-Algorithms: Floyd–Warshall
• Python FAQ: multidimensional lists
• C++ reference: numeric_limits