Thuật toán Dijkstra: đường ngắn nhất với cạnh không âm

Từ số bước sang tổng chi phí

Nếu mọi con đường đều tốn một đơn vị, BFS tìm số cạnh ít nhất. Nhưng giả sử cạnh đi thẳng từ 0 tới 1 tốn 4, còn đi 0 → 2 → 1 tốn 1+2=3. Đường có hai cạnh lại rẻ hơn đường một cạnh. Hàng đợi FIFO theo số bước không còn phản ánh chi phí mà đề hỏi.

Dijkstra duy trì d[v], chi phí tốt nhất hiện biết từ nguồn tới v. Ban đầu d[nguồn]=0, các đỉnh khác chưa đi tới được nên mang giá trị vô cực. Từ đỉnh có d nhỏ nhất đang chờ, ta thử cải thiện các hàng xóm bằng đường vừa tìm được.

Trong bài này cạnh có hướng. Nếu đề cho đường hai chiều, cần thêm cả hai chiều vào danh sách kề. Việc thêm chiều ngược là thay đổi mô hình, không phải một mẹo tùy ý để thuật toán chạy được.

Nới lỏng cạnh nghĩa là gì?

Với cạnh u → v có trọng số w, đường đang biết tới u có chi phí d[u]. Nối thêm cạnh đó cho ứng viên d[u]+w tới v. Nếu ứng viên nhỏ hơn d[v], cập nhật d[v] và đưa cặp khoảng cách mới, đỉnh v vào heap.

Từ nguồn 0, ta biết d[1]=4 và d[2]=1. Khi mở rộng đỉnh 2, cạnh 2 → 1 trọng số 2 tạo ứng viên 1+2=3, nên thay 4 bằng 3. Không cần xóa bản ghi cũ của đỉnh 1 ngay khỏi heap: khi bản ghi đó được lấy ra sau này, ta sẽ nhận ra nó không còn bằng d[1].

Đây là lý do phải phân biệt một đỉnh với một bản ghi trong hàng đợi. Một đỉnh có thể xuất hiện nhiều lần với các khoảng cách từng đúng ở thời điểm được thêm. Mảng d giữ giá trị hiện hành; heap có thể còn chứa lịch sử cũ.

Bảng chạy tay với min-heap

Ví dụ có thêm các cạnh 1 → 3 trọng số 1, 2 → 3 trọng số 5 và 3 → 4 trọng số 3. Dấu ∞ trong bảng nghĩa là chưa có đường được phát hiện.

Hai trạng thái có khóa bằng nhau có thể được lấy theo quy tắc phụ khác. Điều đó không thay đổi khoảng cách cuối. Điều kiện trọng số không âm còn cho phép cạnh trọng số 0; không cần mọi cạnh phải dương nghiêm ngặt.

Vì sao chọn đỉnh gần nhất là an toàn?

Giả sử u được lấy bằng khoảng cách hiện hành nhỏ nhất. Nếu tồn tại đường rẻ hơn tới u qua một đỉnh chưa chốt, xét đỉnh chưa chốt đầu tiên trên đường đó. Tiền nhiệm của nó đã được xử lý, nên thuật toán phải có một ứng viên cho đoạn đầu đường đi. Vì phần đi tiếp có chi phí không âm, ứng viên này không thể lớn hơn toàn bộ đường rẻ hơn tới u, trái với việc u đang nhỏ nhất.

Lập luận hỏng khi phần đi tiếp có thể giảm tổng chi phí. Với cạnh âm, một đỉnh ở xa theo khoảng cách tạm thời vẫn có thể dẫn ngược tới lời giải rẻ hơn cho đỉnh đã chọn. Không dùng Dijkstra làm lời giải có bảo đảm cho loại dữ liệu đó; Bellman–Ford hoặc thứ tự tô-pô trên DAG là những hướng cần xem xét theo đề.

Đoạn code dùng bản ghi lười và không có mảng chốt riêng. Điều đó không biến nó thành thuật toán tổng quát cho cạnh âm: chứng minh và cận thời gian đang dựa trên trọng số không âm, và chu trình âm có thể khiến quá trình cải thiện không dừ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 s){
    vector<vector<pair<int,long long>>>adj(n);
    for(auto[u,v,w]:edges)adj[u].emplace_back(v,w);
    vector<long long>d(n,INF);d[s]=0;
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
    pq.emplace(0,s);
    while(!pq.empty()){
        auto[du,u]=pq.top();pq.pop();if(du!=d[u])continue;
        for(auto[v,w]:adj[u])if(du+w<d[v]){d[v]=du+w;pq.emplace(d[v],v);}
    }
    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):
    import heapq
    adj=[[] for _ in range(n)]
    for u,v,w in edges:adj[u].append((v,w))
    d=[INF]*n;d[s]=0;pq=[(0,s)]
    while pq:
        du,u=heapq.heappop(pq)
        if du!=d[u]:continue
        for v,w in adj[u]:
            if du+w<d[v]:d[v]=du+w;heapq.heappush(pq,(d[v],v))
    return False,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 dữ liệu sẽ in 0 3 1 4 7. Để nhập riêng, dòng đầu có n, m, s; sau đó là m bộ u v w. Đồ thị có hướng, n dương, nguồn s và các đầu cạnh thuộc [0,n). Trọng số là số nguyên không âm. Tệp in INF cho đỉnh không đi tới được.

Trong C++, priority_queue mặc định ưu tiên phần tử lớn. Code dùng bộ so sánh đảo để lấy cặp nhỏ nhất; cặp chứa khoảng cách trước, chỉ số đỉnh sau. Trong Python, heapq đã là min-heap. Đảo vị trí cặp thành đỉnh trước sẽ chọn theo nhãn đỉnh và phá quy tắc mở rộng.

Giá trị INF được chọn là 2 mũ 60. Dữ liệu phải bảo đảm mọi khoảng cách hữu hạn nhỏ hơn INF và các phép cộng trong C++ không vượt miền số nguyên 64 bit. Python có số nguyên lớn, nhưng vẫn cần INF đủ lớn để một đáp án thật không bị nhầm là không tới được. Với đề có giới hạn lớn hơn, phải thiết kế lại giá trị canh và cách cộng.

Ba lỗi heap thường gặp

Trong ví dụ, đỉnh 1 được phát hiện lần đầu bằng 4 nhưng đáp án là 3. Đó là phản ví dụ trực tiếp cho cách đánh dấu ngay lúc đẩy vào heap. Với BFS không trọng số, lần phát hiện đầu đã tối ưu; không được sao chép nguyên quy tắc đánh dấu từ BFS sang thuật toán có trọng số.

Nếu cần khôi phục đường đi, lưu parent[v]=u mỗi khi d[v] được cải thiện. Sau cùng đi ngược parent từ đích về nguồn rồi đảo dãy. Code mẫu tập trung vào khoảng cách và chưa in parent, nên muốn lấy đường phải bổ sung phần này, đồng thời xử lý riêng trường hợp đích không tới được.

Độ phức tạp phải khớp cách cài

Với min-heap lười, có thể tồn tại nhiều bản ghi của cùng một đỉnh. Cận tổng quát phù hợp cả cạnh song song là O((n+m) log(m+1)) thời gian và O(n+m) bộ nhớ kể cả danh sách kề, heap. Với đồ thị đơn, thường viết gọn O((n+m) log n) vì m bị chặn theo n².

Không nên nói heap của phiên bản này luôn chỉ có n phần tử. Nếu cần cấu trúc chỉ giữ một khóa hiện hành mỗi đỉnh, đó là một thiết kế khác như tập có xóa khóa cũ hoặc heap hỗ trợ decrease-key. Với đồ thị dày, bản chọn đỉnh bằng quét mảng O(n²) cũng là lựa chọn cần cân nhắc; heap không tự động tốt nhất cho mọi mật độ.

Tự kiểm và mở rộng

Để tự kiểm tra trên đồ thị nhỏ, bạn có thể đối chiếu kết quả của Dijkstra với thuật toán Bellman-Ford trên các ca nguồn cô lập, cạnh trọng số 0, nhiều đường đi ngắn nhất bằng nhau và trường hợp một đỉnh được giảm khoảng cách nhiều lần. Khi đảo thứ tự nhập cạnh, khoảng cách phải giữ nguyên dù thứ tự xử lý các khóa bằng nhau có thể đổi.

Bài có phiếu giảm giá thường cần thêm trạng thái: đang ở đỉnh nào và đã dùng phiếu hay chưa. Khi trọng số của các chuyển trạng thái vẫn không âm, có thể chạy Dijkstra trên đồ thị trạng thái đó. Chỉ chia đôi một cạnh sau khi đã chọn xong đường ngắn nhất thường bỏ sót đáp án, vì phiếu có thể làm một đường khác trở thành tốt nhất.

Luyện ngay trên Big-O Coding

Hai bài đầu luyện trực tiếp đường ngắn nhất với trọng số không âm. Bài phiếu giảm giá là bước tiếp theo để hiểu rằng thuật toán chạy trên trạng thái được mô hình hóa, không nhất thiết chỉ trên nhãn đỉnh ban đầu.

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

Nguồn tham khảo

• CP-Algorithms: Dijkstra
• CP-Algorithms: Dijkstra on sparse graphs
• C++ reference: priority_queue