Bellman–Ford: đường ngắn nhất có cạnh âm và chu trình âm

Cạnh âm làm thay đổi bài đường đi thế nào?

Hãy coi trọng số là chênh lệch chi phí thay vì chỉ là độ dài con đường. Một bước được hoàn tiền có thể mang giá trị âm. Đường 0 → 1 tốn 4, nhưng 0 → 2 tốn 1 rồi 2 → 1 tốn −2 thì tổng chỉ còn −1. Lúc này chọn đỉnh gần nhất theo quy tắc Dijkstra không có bảo đảm như khi mọi cạnh không âm.

Bellman–Ford dùng cách thẳng hơn: lặp lại việc thử tất cả cạnh. Mỗi khi biết một đường tới u, nối cạnh u → v để thử cải thiện d[v]. Nó chấp nhận việc một khoảng cách bị sửa nhiều lần ở những lượt sau, thay vì dựa vào bước chọn gần nhất để chốt.

Không phải cứ xuất hiện cạnh âm là bài vô nghiệm. Nếu không có chu trình âm liên quan tới đường cần tìm, khoảng cách ngắn nhất vẫn có thể là một số hữu hạn. Ngược lại, một chu trình tổng âm cho phép đi vòng thêm để giảm chi phí mãi; lúc đó không còn giá trị nhỏ nhất hữu hạn cho những đỉnh bị ảnh hưởng.

Nới lỏng một cạnh và điều kiện INF

Với cạnh u → v trọng số w, chỉ xét ứng viên d[u]+w khi u đã đi tới được. Nếu d[u] còn INF, tuyệt đối không cộng rồi coi INF+w là đường thật. Khi w âm, một số canh hữu hạn cộng w có thể nhỏ hơn chính INF và làm xuất hiện khoảng cách giả.

Nếu ứng viên nhỏ hơn d[v], cập nhật d[v]. Dùng dấu nhỏ hơn nghiêm ngặt; đường khác có cùng chi phí không phải một cải thiện cần tiếp tục truyền. Biến changed ghi nhận trong lượt hiện tại có cạnh nào được cải thiện không, phục vụ dừng sớm.

Tệp của bài lưu danh sách cạnh và quét trực tiếp danh sách đó, không cần heap. Dữ liệu đầu vào vì thế cũng tự nhiên: n, m, s rồi m bộ u v w. Đây là đồ thị có hướng; mỗi cạnh nhập vào chỉ có chiều được ghi.

Vì sao n−1 lượt là đủ khi không có chu trình âm?

Một đường đi ngắn nhất hữu hạn có thể chọn thành đường đơn, không lặp đỉnh: nếu có đoạn vòng tổng không âm, bỏ nó không làm đường đắt hơn. Đường đơn trên n đỉnh dùng tối đa n−1 cạnh. Vì thế chỉ cần đủ lượt để truyền thông tin qua tối đa n−1 cạnh.

Cách nhìn quy hoạch động là: sau k lượt, đã tìm được đường tối ưu trong số các đường dùng không quá k cạnh. Mệnh đề này đúng chính xác cho bản dùng hai mảng, mỗi lượt chỉ đọc khoảng cách của lượt trước. Bản code trong bài cập nhật tại chỗ, nên một lượt có thể truyền qua nhiều cạnh nếu thứ tự quét thuận lợi; điều được bảo đảm là nó không truyền chậm hơn bản hai mảng.

Không được kết luận số lượt thực tế luôn bằng số cạnh của đường ngắn nhất. Với chuỗi 0 → 1 → 2 → 3, quét cạnh thuận có thể truyền tới 3 ngay lượt đầu; quét cạnh theo thứ tự ngược cần nhiều lượt hơn. Đáp án không đổi, chỉ tiến độ cải thiện khác nhau.

Chạy tay ví dụ có cạnh âm

Danh sách cạnh theo đúng thứ tự trong code là (0,1,4), (0,2,1), (2,1,−2), (1,3,1), (2,3,5), (3,4,3). Ban đầu d=[0,∞,∞,∞,∞]. Do cập nhật tại chỗ, một lần quét cho diễn biến sau.

Cuối lượt đầu có [0,−1,1,0,3]. Lượt kế tiếp không đổi gì nên dừng sớm. Lượt kiểm chu trình cũng không thấy cạnh cải thiện. Nếu đảo thứ tự cạnh, phải chạy tiếp đến khi ổn định hoặc đủ n−1 lượt; không được coi bảng trên là số lượt chung cho mọi cách nhập.

Phát hiện chu trình âm đúng phạm vi

Sau các lượt chính, quét thêm một lượt. Nếu tồn tại u đi tới được mà d[u]+w nhỏ hơn d[v], thì có chu trình âm đi tới được từ nguồn. Nếu không có chu trình âm như vậy, mọi đường đơn đã được xét đủ và không còn lý do để giảm tiếp.

Ví dụ có 0 → 1 trọng số 1, 1 → 2 trọng số −3 và 2 → 1 trọng số 1. Chu trình 1 → 2 → 1 có tổng −2, nên đi vòng thêm luôn giảm chi phí. Từ nguồn 0, chu trình này liên quan và chương trình báo NEGATIVE_CYCLE.

Đổi ví dụ thành nguồn 0 cô lập, còn chu trình âm chỉ nằm giữa 1 và 2. Điều kiện d[u] khác INF khiến các cạnh trong thành phần đó không được nới lỏng; chương trình không báo chu trình âm từ 0. Nếu đề hỏi có chu trình âm ở bất kỳ đâu, cần bài toán khởi tạo khác, chẳng hạn nguồn phụ nối tới mọi đỉnh hoặc đặt tất cả khoảng cách ban đầu bằng 0 để chỉ kiểm tồn tại.

Ngay cả khi có chu trình âm đi tới được, không phải mọi đỉnh trong đồ thị đều mất khoảng cách hữu hạn. Chỉ các đỉnh đi tới được từ chu trình đó bị ảnh hưởng. Code mẫu chọn báo một cờ chung rồi dừng, chưa phân loại riêng từng đỉnh thành hữu hạn, không tới được và âm vô hạn.

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 s){
    vector<long long>d(n,INF);d[s]=0;
    for(int i=0;i<n-1;++i){bool changed=false;
        for(auto[u,v,w]:edges)if(d[u]!=INF&&d[u]+w<d[v]){d[v]=d[u]+w;changed=true;}
        if(!changed)break;
    }
    for(auto[u,v,w]:edges)if(d[u]!=INF&&d[u]+w<d[v])return {true,d};
    return {false,d};
}

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>>s){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):
    d=[INF]*n;d[s]=0
    for _ in range(n-1):
        changed=False
        for u,v,w in edges:
            if d[u]!=INF and d[u]+w<d[v]:d[v]=d[u]+w;changed=True
        if not changed:break
    return any(d[u]!=INF and d[u]+w<d[v] for u,v,w in edges),d

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    if d:
        n,m=d[:2];off=3;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 sẽ in 0 -1 1 0 3. Với dữ liệu riêng, nhập n, m, s và m cạnh như mô tả; n dương, nguồn và đầu cạnh hợp lệ. Nếu không có chu trình âm đi tới được, chương trình in khoảng cách hoặc INF. Nếu có, chỉ in NEGATIVE_CYCLE.

C++ dùng long long và INF bằng 2 mũ 60. Cần bảo đảm mọi giá trị trung gian trong quá trình nới lỏng nằm trong miền 64 bit, và khoảng cách hữu hạn cần xuất nhỏ hơn INF. Cạnh âm có thể gây nhiều lần giảm trước khi phát hiện chu trình, nên chỉ nhìn giới hạn một cạnh rồi kết luận phép cộng an toàn là chưa đủ. Python tránh tràn số nguyên máy, nhưng vẫn phải chọn INF lớn hơn miền đáp án hữu hạn.

Độ phức tạp và lúc nào không nên chọn

Tối đa n−1 lượt chính và một lượt kiểm, mỗi lượt quét m cạnh: O(nm) thời gian, O(n+m) bộ nhớ gồm danh sách cạnh và khoảng cách. Dừng sớm giúp một số dữ liệu nhưng không đổi cận xấu nhất. Với m=200.000 và n=100.000, nhân hai giới hạn đã là 20 tỷ lần xét cạnh cho một cận thô, nên cần xem đề có cấu trúc nào khác để khai thác.

Không thay Bellman–Ford bằng SPFA rồi hứa chạy nhanh cho mọi đồ thị. Đó là cách tổ chức hàng chờ có hành vi phụ thuộc dữ liệu và vẫn có trường hợp xấu; lựa chọn thuật toán phải dựa trên giới hạn cùng tính chất bài toán.

Tự luyện ba tình huống phân biệt

Trước khi mở bài trên app, hãy tự nhập ba đồ thị nhỏ. Một: chuỗi 0 → 1 trọng số −2, 1 → 2 trọng số 5; đáp án từ 0 là [0,−2,3]. Hai: thêm 2 → 1 trọng số −6; chu trình tổng −1 và phải báo NEGATIVE_CYCLE. Ba: giữ chu trình đó nhưng bỏ đường từ nguồn 0 tới nó; chỉ nguồn có khoảng cách 0, hai đỉnh kia INF và không có cờ lỗi từ nguồn.

Khi tự kiểm tra trên đồ thị nhỏ, bạn nên thử đồ thị có cạnh âm nhưng không có chu trình âm, chu trình âm đi tới được từ nguồn, chu trình âm nằm ở thành phần tách biệt và đồ thị không có cạnh. Các ca này giúp phát hiện nhanh lỗi quên điều kiện dist[u] != INF hoặc lỗi báo nhầm chu trình âm không đi tới được từ nguồn.

Luyện ngay trên Big-O Coding

Bài dưới tập trung đúng phần khó nhất của thuật toán: nhận ra chu trình âm bằng lượt nới lỏng thêm. Hãy đọc rõ đề muốn tìm chu trình ở bất kỳ đâu hay chỉ từ một nguồn để chọn cách khởi tạo.

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

Nguồn tham khảo

• CP-Algorithms: Bellman–Ford
• CP-Algorithms: Finding a negative cycle
• C++ reference: numeric_limits