Bài 29: Đường đi ngắn nhất trong C++ và Python: Dijkstra, BFS 0-1, Floyd-Warshall và Bellman-Ford

Series: Thuật toán nâng cao Độ khó: Khá Bài 29 / Thuật toán nâng cao Đồ thị Đường đi ngắn nhất

// Thuật toán nâng cao · Bài 29

Đường đi ngắn nhất: Dijkstra, BFS 0-1, Floyd–Warshall và Bellman–Ford

Khi mỗi con đường có độ dài riêng, BFS không còn đúng nữa. Bốn thuật toán trong bài này sẽ trả lời câu hỏi “đi đường nào nhanh nhất” cho mọi kiểu đồ thị hay gặp trong đề thi.

Lời mở đầu

Ở bài 21 em đã biết lưu đồ thị bằng danh sách kề và dùng BFS để tìm đường đi qua ít cạnh nhất, kể cả loang trên lưới. Nhưng ngoài đời, các con đường đâu có dài bằng nhau: đi từ nhà tới trường có thể qua 3 ngã tư mà vẫn nhanh hơn đường chỉ có 1 ngã tư nhưng hay tắc. Khi mỗi cạnh mang một trọng số (độ dài, thời gian, chi phí) thì “ít cạnh nhất” không còn là “ngắn nhất” nữa.

Bài này là một trong những bài quan trọng nhất của cả series: đề HSG cấp tỉnh gần như năm nào cũng có một bài đường đi ngắn nhất, có khi giấu dưới dạng lưới, dạng trạng thái hay dạng “chi phí nhỏ nhất”. Mình sẽ dùng lại priority_queue ở bài 11, deque ở bài 25 và tư duy quy hoạch động ở bài 19 (Floyd chính là một bài quy hoạch động).

Bài 24Chia để trị, sắp xếp nhanhBài 25Ngăn xếp, hàng đợi đơn điệuBài 26Toán modulo và tổ hợpBài 27Quy hoạch động nâng caoBài 28Xâu: Hash và KMPBài 29Đường đi ngắn nhấtBài 30DSU và cây khungBài 31Fenwick, Segment TreeBài 32Tổng ôn và đề thi thử

Trong bài này bạn sẽ học: đồ thị có trọng số và vì sao BFS cho kết quả sai; phép nới lỏng (relax), viên gạch của mọi thuật toán đường đi ngắn nhất; thuật toán Dijkstra với hàng đợi ưu tiên trong $O((n + m) \log n)$ và cách truy vết đường đi; BFS 0-1 với deque cho đồ thị chỉ có cạnh 0 và 1; Floyd–Warshall tính khoảng cách giữa mọi cặp đỉnh trong $O(n^3)$; Bellman–Ford cho trọng số âm và cách phát hiện chu trình âm; bảng chọn thuật toán theo giới hạn đề. Có khung chạy tay Dijkstra và Floyd, 3 mô phỏng tương tác và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Trọng số, nới lỏngPhần 2DijkstraPhần 3BFS 0-1Phần 4Floyd–WarshallPhần 5Bellman–Ford, chọn thuật toánBài tập8 bài + gợi ý

Phần 1Đồ thị có trọng số và phép nới lỏng

Đồ thị có trọng số là đồ thị mà mỗi cạnh $(u, v)$ mang thêm một số $w$ gọi là trọng số (độ dài). Độ dài một đường đi là tổng trọng số các cạnh trên đường. Bài toán: tìm đường đi có tổng nhỏ nhất từ đỉnh nguồn $s$ tới các đỉnh khác. Ta gọi $dist[v]$ là độ dài đường đi ngắn nhất từ $s$ tới $v$.

Lưu đồ thị vẫn bằng danh sách kề như bài 21, chỉ khác là mỗi phần tử giờ là một cặp (đỉnh kề, trọng số): vector<pair<int,int>> adj[N] trong C++, adj[u].append((v, w)) trong Python.

Vì sao BFS sai? BFS đi theo từng “lớp”: đỉnh nào ít cạnh hơn thì tới trước. Nó đúng khi mọi cạnh dài bằng nhau. Nhìn ví dụ dưới đây:

Hình 1. BFS từ đỉnh 1 gặp đỉnh 3 ngay ở lớp đầu tiên (qua cạnh dài 10) và chốt dist[3] = 10. Nhưng đường vòng 1 → 2 → 3 qua hai cạnh chỉ dài 5.

Bài học: với trọng số, đỉnh “tới trước theo số cạnh” chưa chắc là đỉnh “gần nhất theo độ dài”. Ta cần một cách khác để cập nhật khoảng cách mỗi khi phát hiện đường tốt hơn.

Phép nới lỏng (relax). Giả sử ta đang biết một đường từ $s$ tới $u$ dài $dist[u]$, và có cạnh $u \to v$ trọng số $w$. Vậy có một đường tới $v$ dài $dist[u] + w$: đi tới $u$ rồi đi tiếp cạnh đó. Nếu nó ngắn hơn $dist[v]$ đang biết thì cập nhật:

Hình 2. Nới lỏng cạnh u → v: thử “đi qua u” xem có rẻ hơn con đường tới v đang biết không.

Khuôn mẫu: phép nới lỏng

if(dist[u] + w < dist[v]){
    dist[v] = dist[u] + w;     // tìm được đường tốt hơn tới v
    trace[v] = u;              // (nếu cần in đường đi) nhớ đỉnh đứng trước v
}

Ban đầu $dist[s] = 0$, các đỉnh khác $dist = \infty$. Mọi thuật toán trong bài này đều chỉ là các thứ tự khác nhau để gọi phép nới lỏng: Dijkstra nới lỏng theo thứ tự đỉnh gần nhất, Bellman–Ford nới lỏng tất cả các cạnh nhiều lượt, Floyd nới lỏng qua từng đỉnh trung gian.

Chọn giá trị vô cùng cho cẩn thận

Trọng số tới $10^9$ và đường đi dài tới $2 \cdot 10^5$ cạnh thì độ dài có thể tới $2 \cdot 10^{14}$, vượt int. Dùng long long và INF = 1e18. Đừng dùng LLONG_MAX làm vô cùng: LLONG_MAX + w bị tràn số thành số âm, phép so sánh sẽ sai bét.

Phần 2Thuật toán Dijkstra

Ý tưởng của Dijkstra rất giống BFS, chỉ thay “hàng đợi thường” bằng “luôn lấy đỉnh có $dist$ nhỏ nhất chưa xử lý”:

1. Khởi tạo $dist[s] = 0$, các đỉnh khác $\infty$.
2. Lấy ra đỉnh $u$ chưa xử lý có $dist[u]$ nhỏ nhất. Lúc này $dist[u]$ đã là đáp án cuối cùng, ta “chốt” nó.
3. Nới lỏng mọi cạnh đi ra từ $u$.
4. Lặp lại tới khi không còn đỉnh nào.

Vì sao đỉnh nhỏ nhất thì chốt được? Mọi đường khác tới $u$ đều phải đi qua một đỉnh $x$ chưa chốt nào đó, mà $dist[x] \ge dist[u]$; đi tiếp từ $x$ tới $u$ chỉ cộng thêm trọng số không âm, nên không thể ngắn hơn $dist[u]$. Lý luận này dùng đúng một giả thiết: mọi trọng số $\ge 0$.

Lấy đỉnh nhỏ nhất thật nhanh. Duyệt cả mảng để tìm min thì mất $O(n)$ mỗi lần, tổng $O(n^2)$. Dùng hàng đợi ưu tiên chứa các cặp $(dist, đỉnh)$ thì mỗi lần lấy ra chỉ mất $O(\log n)$. Có một vấn đề: khi $dist[v]$ giảm, cặp cũ của $v$ vẫn nằm trong hàng đợi và priority_queue không xoá được phần tử ở giữa. Mẹo xoá lười (lazy deletion): cứ đẩy cặp mới vào, còn khi lấy ra cặp $(d, u)$ mà $d > dist[u]$ thì biết ngay đó là cặp cũ và bỏ qua.

Em chạy thử mô phỏng: nhãn d=… trên mỗi đỉnh là $dist$ hiện tại, hàng dưới là nội dung hàng đợi ưu tiên. Em có thể sửa danh sách cạnh, đổi đỉnh xuất phát để thử đồ thị của riêng mình:

MÔ PHỎNGDijkstra từng bước trên đồ thị: lấy đỉnh gần nhất, nới lỏng các cạnhSửa danh sách cạnh vô hướng (mỗi dòng “u v w”), số đỉnh và đỉnh xuất phát rồi bấm Tiếp / Tự chạy.

Số đỉnh nXuất phátCạnh u v w1 2 7 1 3 9 1 6 14 2 3 10 2 4 15 3 4 11 3 6 2 4 5 6 5 6 9

ChậmVừaNhanh

đỉnh vừa lấy rađang có trong hàng đợiđã chốt khoảng cách / cạnh của cây đường đicạnh nới lỏng không thành công

Lấy ra	Chốt	Nới lỏng thành công	Hàng đợi sau bước này
(0, 1)	dist[1] = 0	2: ∞ → 4, 3: ∞ → 1	(1,3) (4,2)
(1, 3)	dist[3] = 1	2: 4 → 3, 4: ∞ → 6	(3,2) (4,2) (6,4)
(3, 2)	dist[2] = 3	4: 6 → 4	(4,2) (4,4) (6,4)
(4, 2)	cặp cũ, bỏ qua	–	(4,4) (6,4)
(4, 4)	dist[4] = 4	5: ∞ → 7	(6,4) (7,5)
(6, 4)	cặp cũ, bỏ qua	–	(7,5)
(7, 5)	dist[5] = 7	–	rỗng: xong

Bảng 1. Dijkstra từ đỉnh 1 trên đồ thị 5 đỉnh với các cạnh 1–2 (4), 1–3 (1), 3–2 (2), 2–4 (1), 3–4 (5), 4–5 (3). Hai lần lấy ra cặp cũ đã bị bỏ qua nhờ phép kiểm tra d > dist[u].

Xem code C++ / Python: dijkstra với hàng đợi ưu tiên (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
vector<pair<int, int>> adj[200005];      // adj[u] = {(v, w)}
long long dist[200005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});        // đồ thị vô hướng
    }
    for(int v = 1; v <= n; v++) dist[v] = INF;
    // hàng đợi ưu tiên lấy cặp (khoảng cách, đỉnh) NHỎ NHẤT trước
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;        // cặp cũ (đã có đường tốt hơn): bỏ qua
        for(auto [v, w] : adj[u])
            if(dist[u] + w < dist[v]){   // nới lỏng cạnh u -> v
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
    }
    for(int v = 1; v <= n; v++) cout << (dist[v] == INF ? -1 : dist[v]) << " ";
    return 0;
}

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
        adj[u].append((v, w))
        adj[v].append((u, w))            # đồ thị vô hướng
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[1] = 0
    pq = [(0, 1)]                        # heapq luôn lấy cặp nhỏ nhất
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:                  # cặp cũ: bỏ qua
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:          # nới lỏng cạnh u -> v
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    print(' '.join(str(x) if x != INF else '-1' for x in dist[1:]))

main()

Giờ em tự chạy tay đúng đồ thị ở Bảng 1, theo từng dòng code C++. Để ý lúc lấy ra cặp (4, 2): dòng if(d > dist[u]) continue; phát huy tác dụng.

C++▶ Chạy tay từng dòng codeDijkstra: lấy cặp (d, u) nhỏ nhất, bỏ qua cặp cũ, nới lỏng các cạnh ra từ u (ô vàng: u, ô đỏ: v đang xét, ô xanh lá: đã chốt).

Dữ liệu vào (stdin) – sửa thoải mái5 6 1 2 4 1 3 1 3 2 2 2 4 1 3 4 5 4 5 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4const long long INF = 1e18;

5vector<pair<int, int>> adj[105];

6long long dist[105];

7

8int main(){

9 int n, m;

10 cin >> n >> m;

11 for(int i = 0; i < m; i++){

12 int u, v, w;

13 cin >> u >> v >> w;

14 adj[u].push_back({v, w});

15 adj[v].push_back({u, w});

16 }

17 for(int v = 1; v <= n; v++) dist[v] = INF;

18 priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

19 dist[1] = 0; pq.push({0, 1});

20 while(!pq.empty()){

21 auto [d, u] = pq.top(); pq.pop();

22 if(d > dist[u]) continue;

23 for(auto [v, w] : adj[u]){

24 if(dist[u] + w < dist[v]){

25 dist[v] = dist[u] + w;

26 pq.push({dist[v], v});

27 }

28 }

29 }

30 for(int v = 1; v <= n; v++) cout << (dist[v] == INF ? -1 : dist[v]) << " ";

31 return 0;

32}

ChậmVừaNhanhRất nhanh

Độ phức tạp. Mỗi cạnh được nới lỏng thành công nhiều nhất một lần mỗi chiều, mỗi lần đẩy một cặp vào hàng đợi, nên hàng đợi có không quá $O(m)$ phần tử. Mỗi thao tác hàng đợi tốn $O(\log m) = O(\log n)$. Tổng cộng $O((n + m) \log n)$: với $n, m = 2 \cdot 10^5$ chỉ khoảng vài triệu phép tính.

Truy vết đường đi. Muốn in ra chính con đường chứ không chỉ độ dài, mỗi lần nới lỏng thành công cạnh $u \to v$ ta ghi trace[v] = u: “tới $v$ tốt nhất là đi từ $u$”. Xong Dijkstra, đi ngược từ đích: $t \to trace[t] \to trace[trace[t]] \to \ldots$ cho tới khi về nguồn $s$, rồi đảo ngược dãy. Các cạnh $(trace[v], v)$ tạo thành cây đường đi ngắn nhất (các cạnh xanh lá trong mô phỏng).

Xem code C++ / Python: dijkstra kèm truy vết đường đi từ s tới t (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
vector<pair<int, int>> adj[200005];
long long dist[200005];
int trace_[200005];                      // trace_[v] = đỉnh đứng ngay trước v

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for(int v = 1; v <= n; v++) dist[v] = INF;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[s] = 0; trace_[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto [v, w] : adj[u])
            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                trace_[v] = u;           // ghi nhớ: tới v tốt nhất là đi từ u
                pq.push({dist[v], v});
            }
    }
    if(dist[t] == INF){ cout << -1; return 0; }
    vector<int> path;
    for(int v = t; v != 0; v = trace_[v]) path.push_back(v);   // lần ngược từ t về s
    reverse(path.begin(), path.end());
    cout << dist[t] << "\n";
    for(int v : path) cout << v << " ";
    return 0;
}

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m, s, t = int(data[0]), int(data[1]), int(data[2]), int(data[3])
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, w = int(data[4 + 3 * i]), int(data[5 + 3 * i]), int(data[6 + 3 * i])
        adj[u].append((v, w))
        adj[v].append((u, w))
    INF = float('inf')
    dist = [INF] * (n + 1)
    trace = [0] * (n + 1)                # trace[v] = đỉnh đứng ngay trước v
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                trace[v] = u             # tới v tốt nhất là đi từ u
                heapq.heappush(pq, (dist[v], v))
    if dist[t] == INF:
        print(-1)
        return
    path, v = [], t
    while v != 0:                        # lần ngược từ t về s
        path.append(v)
        v = trace[v]
    print(dist[t])
    print(*path[::-1])

main()

Trọng số âm thì Dijkstra sai

Xét cạnh có hướng 1 → 2 (2), 1 → 3 (3), 3 → 2 (−2). Dijkstra lấy đỉnh 2 trước với $dist = 2$ và “chốt” nó, nhưng đường 1 → 3 → 2 chỉ dài $3 - 2 = 1$. Lý luận “đi tiếp chỉ làm đường dài thêm” sụp đổ ngay khi có cạnh âm. Bản xoá lười đôi khi vô tình sửa lại được ở ví dụ nhỏ, nhưng có thể phải xử lý một đỉnh rất nhiều lần (chạy cực lâu), còn nếu có chu trình âm thì lặp vô hạn. Gặp trọng số âm, em dùng Bellman–Ford ở phần 5.

Ba lỗi hay gặp khi cài Dijkstra

1. Quên greater<…>: priority_queue mặc định lấy phần tử lớn nhất, thuật toán vẫn chạy ra kết quả nhưng chậm khủng khiếp hoặc sai. Mẹo khác là đẩy {-dist, v} vào hàng đợi mặc định.
2. Đặt cặp là {v, dist} thay vì {dist, v}: hàng đợi sẽ so sánh theo số hiệu đỉnh.
3. Thiếu dòng if(d > dist[u]) continue;: kết quả vẫn đúng nhưng một đỉnh bị duyệt cạnh nhiều lần, có test sẽ quá thời gian.

Phần 3BFS 0-1 với deque

Rất nhiều bài trên lưới có dạng: đi thế này thì miễn phí, đi thế kia thì tốn 1. Ví dụ lưới mũi tên: mỗi ô có một mũi tên, đi theo mũi tên không tốn gì, muốn đi hướng khác phải đổi mũi tên với giá 1. Hỏi ít nhất phải đổi bao nhiêu mũi tên để đi từ góc trên trái tới góc dưới phải.

Hình 3. Đi theo mũi tên từ ô (1, 1) sang phải tới ô (1, 3), xuống ô (2, 3) thì mũi tên chỉ sang trái. Đổi nó thành ↓ (tốn 1) là tới được ô đích. Đáp án: 1.

Đây là đồ thị mà mọi cạnh chỉ có trọng số 0 hoặc 1. Dùng Dijkstra được, nhưng có cách nhanh hơn và gọn hơn: BFS 0-1. Thay hàng đợi ưu tiên bằng hàng đợi hai đầu deque:

• Nới lỏng thành công qua cạnh 0: đỉnh mới có cùng khoảng cách với đỉnh đang xét, cho nó chen lên đầu (push_front).
• Nới lỏng thành công qua cạnh 1: đỉnh mới xa hơn 1, cho nó xếp xuống cuối (push_back).
• Luôn lấy ra ở đầu deque.

Nhờ vậy deque lúc nào cũng có dạng: các đỉnh khoảng cách $d$ ở phía đầu, các đỉnh khoảng cách $d + 1$ ở phía cuối, tức là nó tự sắp xếp như hàng đợi ưu tiên mà không cần $\log$. Độ phức tạp chỉ là $O(n + m)$, đúng như BFS thường.

Ví dụ dễ hình dung nhất là mê cung phá tường: lưới gồm ô trống . và ô tường #, đi vào ô trống tốn 0, đi vào ô tường tốn 1 (phải phá nó). Hỏi ít nhất phải phá bao nhiêu bức tường. Em xem deque thay đổi thế nào trong mô phỏng, chú ý ô trống luôn được chen lên đầu:

MÔ PHỎNGBFS 0-1 với deque: phá ít tường nhất để ra khỏi mê cungNhập lưới (tối đa 6 hàng × 8 cột, các hàng cách nhau bởi dấu cách). Số trong ô là khoảng cách đã tìm được.

Lưới

ChậmVừaNhanh

ô vừa lấy rađang trong dequeđã chốttường chưa tới

Xem code C++ / Python: bfs 0-1 trên lưới phá tường (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int R, C;
string g[1005];
int dist[1005][1005];
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> R >> C;
    for(int i = 0; i < R; i++) cin >> g[i];
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++) dist[i][j] = INT_MAX;
    deque<pair<int, int>> dq;
    dist[0][0] = (g[0][0] == '#');               // ô xuất phát là tường cũng phải phá
    dq.push_back({0, 0});
    while(!dq.empty()){
        auto [r, c] = dq.front(); dq.pop_front();
        for(int k = 0; k < 4; k++){
            int nr = r + dr[k], nc = c + dc[k];
            if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            int w = (g[nr][nc] == '#');          // vào ô tường tốn 1, ô trống tốn 0
            if(dist[r][c] + w < dist[nr][nc]){
                dist[nr][nc] = dist[r][c] + w;
                if(w == 0) dq.push_front({nr, nc});   // cạnh 0: chen lên ĐẦU
                else dq.push_back({nr, nc});          // cạnh 1: xếp xuống CUỐI
            }
        }
    }
    cout << dist[R - 1][C - 1];
    return 0;
}

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    R, C = int(data[0]), int(data[1])
    g = ''.join(data[2:2 + R])                    # ô (r, c) là g[r * C + c]
    N = R * C
    INF = float('inf')
    dist = [INF] * N
    dist[0] = 1 if g[0] == '#' else 0
    dq = deque([0])
    while dq:
        u = dq.popleft()
        r, c = divmod(u, C)
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < R and 0 <= nc < C:
                v = nr * C + nc
                w = 1 if g[v] == '#' else 0       # vào ô tường tốn 1
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    if w == 0:
                        dq.appendleft(v)          # cạnh 0: chen lên đầu
                    else:
                        dq.append(v)              # cạnh 1: xếp xuống cuối
    print(dist[N - 1])

main()

BFS 0-1 có cần mảng “đã chốt” không?

Không bắt buộc. Một ô có thể được đưa vào deque vài lần (mỗi lần $dist$ giảm), nhưng trọng số chỉ 0 hoặc 1 nên mỗi ô bị lấy ra không quá vài lần, tổng vẫn $O(n + m)$. Nếu muốn chắc chắn, em có thể thêm mảng done giống Dijkstra: lấy ra ô đã chốt thì continue.

Tổng quát hoá: trọng số 0 … K

Nếu cạnh có trọng số là số nguyên nhỏ từ 0 tới $K$ (ví dụ $K \le 10$) thì có thể dùng $K + 1$ hàng đợi xoay vòng (Dial). Nhưng khi đi thi, Dijkstra thường đã đủ nhanh, chỉ dùng BFS 0-1 khi trọng số đúng là 0 và 1, hoặc đề có giới hạn rất lớn (lưới $2000 \times 2000$).

Phần 4Floyd–Warshall: khoảng cách giữa mọi cặp đỉnh

Dijkstra cho khoảng cách từ một đỉnh nguồn. Nếu đề hỏi hàng nghìn truy vấn “khoảng cách từ $u$ tới $v$” với $n$ nhỏ (tầm $n \le 400$), tiện nhất là tính sẵn cả bảng $d[i][j]$ cho mọi cặp. Floyd–Warshall làm việc đó chỉ với ba vòng for.

Ý tưởng quy hoạch động. Gọi $d_k[i][j]$ là đường đi ngắn nhất từ $i$ tới $j$ mà các đỉnh trung gian (không tính hai đầu) chỉ được lấy trong $\{1, 2, \ldots, k\}$. Khi cho phép thêm đỉnh $k$, đường tốt nhất hoặc không đi qua $k$ (giữ nguyên $d_{k-1}[i][j]$), hoặc đi qua $k$ đúng một lần: $i \leadsto k \leadsto j$. Vậy:

$d_k[i][j] = \min\left(d_{k-1}[i][j],\; d_{k-1}[i][k] + d_{k-1}[k][j]\right)$

Bắt đầu từ $d_0$ = ma trận cạnh ($0$ trên đường chéo, $w$ nếu có cạnh, $\infty$ nếu không), lần lượt cho $k = 1, 2, \ldots, n$. Một mẹo hay: ta chỉ cần một bảng $d$, cập nhật đè lên luôn, vì trong vòng $k$ hàng $k$ và cột $k$ không đổi ($d[k][k] = 0$).

MÔ PHỎNGFloyd–Warshall: ma trận khoảng cách thay đổi theo từng đỉnh trung gian kNhập số đỉnh (tối đa 6) và các cạnh có hướng “u v w”. Mỗi bước chỉ dừng ở những ô thực sự được cải thiện.

Số đỉnh nCạnh có hướng u v w1 2 4 1 3 11 2 3 2 3 4 3 4 1 5 2 4 9

ChậmVừaNhanh

hàng k, cột kd[i][k] và d[k][j]ô vừa được cải thiện

Xem code C++ / Python: floyd–warshall trả lời nhiều truy vấn (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
long long d[505][505];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for(int i = 0; i < m; i++){
        int u, v; long long w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);               // có thể có nhiều cạnh u -> v
    }
    for(int k = 1; k <= n; k++)                  // k (đỉnh trung gian) PHẢI ở ngoài cùng
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
    while(q--){
        int u, v;
        cin >> u >> v;
        cout << (d[u][v] == INF ? -1 : d[u][v]) << "\n";
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m, q = int(data[0]), int(data[1]), int(data[2])
    INF = 10 ** 18
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    p = 3
    for _ in range(m):
        u, v, w = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]); p += 3
        d[u][v] = min(d[u][v], w)
    for k in range(n):                           # k ở ngoài cùng
        dk = d[k]
        for i in range(n):
            di = d[i]
            dik = di[k]
            if dik == INF:
                continue
            # cả hàng i được cập nhật một lần bằng list comprehension cho nhanh
            d[i] = [x if x <= dik + y else dik + y for x, y in zip(di, dk)]
    out = []
    for _ in range(q):
        u, v = int(data[p]) - 1, int(data[p + 1]) - 1; p += 2
        out.append(str(d[u][v]) if d[u][v] < INF else '-1')
    print('\n'.join(out))

main()

Chạy tay để thấy ma trận thay đổi theo từng $k$ (mỗi hàng d[i] là một hàng của ma trận, cột 0 không dùng):

C++▶ Chạy tay từng dòng codeFloyd–Warshall: với mỗi k, thử đi i → k → j cho mọi cặp (i, j). Chỉ dừng ở những ô được cải thiện.

Dữ liệu vào (stdin) – sửa thoải mái4 6 3 1 2 4 1 3 11 2 3 2 3 4 3 4 1 5 2 4 9 1 4 4 3 3 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4const long long INF = 1e18;

5long long d[105][105];

6

7int main(){

8 int n, m, q;

9 cin >> n >> m >> q;

10 for(int i = 1; i <= n; i++)

11 for(int j = 1; j <= n; j++)

12 d[i][j] = (i == j ? 0 : INF);

13 for(int i = 0; i < m; i++){

14 int u, v; long long w;

15 cin >> u >> v >> w;

16 d[u][v] = min(d[u][v], w);

17 }

18 for(int k = 1; k <= n; k++)

19 for(int i = 1; i <= n; i++)

20 for(int j = 1; j <= n; j++)

21 if(d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j])

22 d[i][j] = d[i][k] + d[k][j];

23 while(q--){

24 int u, v;

25 cin >> u >> v;

26 cout << (d[u][v] == INF ? -1 : d[u][v]) << "\n";

27 }

28 return 0;

29}

ChậmVừaNhanhRất nhanh

Vòng k phải ở ngoài cùng

Thứ tự đúng là for k → for i → for j. Nếu đặt k vào trong (ví dụ for i → for j → for k), khi tính $d[i][j]$ ta dùng $d[i][k]$ và $d[k][j]$ chưa được tính xong, kết quả sai mà code vẫn chạy bình thường, rất khó phát hiện. Hãy nhớ: $k$ là “số giai đoạn” của quy hoạch động, giai đoạn phải đi trước.

Độ phức tạp $O(n^3)$ thời gian, $O(n^2)$ bộ nhớ. $n = 400$ cho $6{,}4 \cdot 10^7$ phép tính, C++ chạy chưa tới 0,2 giây; Python thì nên giữ $n \le 200$ và cập nhật cả hàng bằng list comprehension như code trên. Floyd còn xử lý được cạnh âm (miễn không có chu trình âm), và nếu sau khi chạy có $d[i][i] < 0$ thì đỉnh $i$ nằm trên một chu trình âm.

Phần 5Bellman–Ford, chu trình âm và chọn thuật toán

Bellman–Ford là thuật toán “chân chất” nhất: nới lỏng tất cả các cạnh, lặp lại $n - 1$ lượt. Không cần hàng đợi, không cần thứ tự gì cả.

Vì sao $n - 1$ lượt là đủ? Nếu không có chu trình âm, đường đi ngắn nhất không lặp đỉnh nên có không quá $n - 1$ cạnh $s = v_0 \to v_1 \to \cdots \to v_k$. Lượt 1 chắc chắn nới đúng cạnh $v_0 \to v_1$, lượt 2 chắc chắn nới đúng $v_1 \to v_2$, … sau lượt $k$ thì $dist[v_k]$ đã đúng. Thời gian $O(n \cdot m)$.

Phát hiện chu trình âm. Chu trình âm là chu trình có tổng trọng số âm: cứ đi vòng mãi thì đường càng “ngắn”, không có đáp án. Sau $n - 1$ lượt, nếu lượt thứ $n$ vẫn còn nới lỏng được cạnh nào thì chắc chắn có chu trình âm đi tới được từ $s$.

Lượt	dist[1]	dist[2]	dist[3]	dist[4]	dist[5]	Ghi chú
đầu	0	∞	∞	∞	∞
1	0	1	2	4	2	duyệt cạnh theo thứ tự nhập, cạnh sau dùng ngay kết quả cạnh trước
2	0	1	2	4	2	không đổi gì → dừng sớm

Bảng 2. Bellman–Ford từ đỉnh 1 với các cạnh có hướng 1→2 (4), 1→3 (2), 3→2 (−1), 2→4 (3), 4→5 (−2), 3→5 (6). Cạnh 3→2 âm làm dist[2] giảm từ 4 xuống 1.

Xem code C++ / Python: bellman–ford và phát hiện chu trình âm (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
struct Edge { int u, v; long long w; };

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<Edge> e(m);
    for(auto &x : e) cin >> x.u >> x.v >> x.w;          // cạnh có hướng, w có thể âm
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    for(int round = 1; round <= n - 1; round++){         // tối đa n - 1 lượt
        bool changed = false;
        for(auto &x : e)
            if(dist[x.u] != INF && dist[x.u] + x.w < dist[x.v]){
                dist[x.v] = dist[x.u] + x.w;
                changed = true;
            }
        if(!changed) break;                              // ổn định sớm thì dừng
    }
    for(auto &x : e)                                     // lượt thứ n: còn nới được?
        if(dist[x.u] != INF && dist[x.u] + x.w < dist[x.v]){
            cout << "NEGATIVE CYCLE";
            return 0;
        }
    for(int v = 1; v <= n; v++){
        if(dist[v] == INF) cout << "INF ";
        else cout << dist[v] << " ";
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    e = [(int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])) for i in range(m)]
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[1] = 0
    for _ in range(n - 1):                       # tối đa n - 1 lượt
        changed = False
        for u, v, w in e:
            if dist[u] + w < dist[v]:            # INF + w vẫn là INF nên không cần kiểm tra
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    for u, v, w in e:                            # lượt thứ n: còn nới được?
        if dist[u] + w < dist[v]:
            print('NEGATIVE CYCLE')
            return
    print(' '.join('INF' if x == INF else str(x) for x in dist[1:]))

main()

Chu trình âm “không với tới” thì sao?

Code trên chỉ báo chu trình âm nếu nó đi tới được từ đỉnh 1 (test thứ ba: chu trình 3 ⇄ 4 âm nhưng không đi tới được, nên vẫn in bình thường). Muốn kiểm tra cả đồ thị có chu trình âm hay không, gán $dist[v] = 0$ cho mọi đỉnh trước khi chạy, giống như thêm một nguồn ảo nối tới tất cả (bài tập 8).

Chọn thuật toán nào? Đây là bảng em nên thuộc lòng trước khi đi thi:

Thuật toán	Độ phức tạp	Trọng số	Trả lời	Dùng khi
BFS (bài 21)	$O(n + m)$	mọi cạnh bằng nhau	một nguồn	$n, m \le 10^6$
BFS 0-1	$O(n + m)$	chỉ 0 và 1	một nguồn	lưới đổi hướng, phá tường
Dijkstra	$O((n + m) \log n)$	$\ge 0$	một nguồn	$n, m \le 2 \cdot 10^5$ (mặc định)
Bellman–Ford	$O(n \cdot m)$	có thể âm	một nguồn, báo chu trình âm	$n \cdot m \le 10^7$
Floyd–Warshall	$O(n^3)$	có thể âm	mọi cặp đỉnh	$n \le 400$, nhiều truy vấn

Bảng 3. Chọn thuật toán đường đi ngắn nhất theo trọng số và giới hạn của đề.

Mẹo: chạy Dijkstra ngược

Đề hỏi “khoảng cách từ mọi đỉnh tới đỉnh $t$” trên đồ thị có hướng? Đảo chiều mọi cạnh rồi chạy Dijkstra một lần từ $t$, thay vì chạy $n$ lần. Đề có nhiều nguồn (ví dụ nhiều trạm cứu hoả, hỏi mỗi nhà cách trạm gần nhất bao xa)? Đẩy tất cả nguồn vào hàng đợi với $dist = 0$ ngay từ đầu (Dijkstra đa nguồn).

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

• Covid (ICTU P58) (Trung bình)
• Nhà Từ Thiện Swyrin (Trung bình)
• The Time When the Network Becomes Idle (LeetCode 2039) (Trung bình)
• Bin Laden (Khá)
• Hội Chợ (Khó)
• Dịch chuyển tức thời (Khó)

Xem toàn bộ bài cùng chủ đề: nhãn Đường đi ngắn nhất.

Bài tậpLuyện đường đi ngắn nhất

Bài 1Khoảng cách từ đỉnh 1Dễ

Cho đồ thị có hướng $n$ đỉnh, $m$ cạnh ($1 \le n, m \le 2 \cdot 10^5$), cạnh thứ $i$ đi từ $u_i$ tới $v_i$ với độ dài $w_i$ ($1 \le w_i \le 10^9$). In ra $n$ số: khoảng cách ngắn nhất từ đỉnh 1 tới đỉnh $1, 2, \ldots, n$; đỉnh không tới được in $-1$.

Input

6 6
1 2 3
1 3 8
2 3 2
3 4 1
4 2 4
2 5 10

Output

0 3 5 6 13 -1

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dijkstra như phần 2, chỉ khác là đồ thị có hướng nên mỗi cạnh chỉ thêm một chiều. Tới đỉnh 3 thì đi 1 → 2 → 3 (3 + 2 = 5) rẻ hơn cạnh trực tiếp dài 8; đỉnh 6 không có cạnh nào đi tới nên in $-1$. Khoảng cách có thể tới $2 \cdot 10^{14}$, nhớ dùng long long.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
vector<pair<int, int>> adj[200005];
long long dist[200005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});            // có hướng: chỉ một chiều
    }
    for(int v = 1; v <= n; v++) dist[v] = INF;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[1] = 0; pq.push({0, 1});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto [v, w] : adj[u])
            if(d + w < dist[v]){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
    }
    for(int v = 1; v <= n; v++) cout << (dist[v] == INF ? -1 : dist[v]) << " ";
    return 0;
}

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
        adj[u].append((v, w))                # có hướng: chỉ một chiều
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[1] = 0
    pq = [(0, 1)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    print(' '.join(str(x) if x != INF else '-1' for x in dist[1:]))

main()

Bài 2In đường đi ngắn nhấtDễ

Cho đồ thị vô hướng $n$ đỉnh, $m$ cạnh ($n, m \le 2 \cdot 10^5$, $1 \le w \le 10^9$) và hai đỉnh $s, t$. Nếu không có đường từ $s$ tới $t$, in $-1$. Ngược lại, dòng đầu in độ dài đường đi ngắn nhất, dòng hai in các đỉnh trên đường theo thứ tự từ $s$ tới $t$. Dữ liệu đảm bảo đường đi ngắn nhất (nếu có) là duy nhất.

Input

6 7 1 6
1 2 2
2 3 2
1 4 5
3 6 3
4 5 1
5 6 3
2 5 4

Output

7
1 2 3 6

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dijkstra từ $s$ kèm mảng trace như phần 2: nới lỏng thành công cạnh $u \to v$ thì ghi trace[v] = u. Xong thì lần ngược từ $t$ về $s$ và đảo dãy. Trong ví dụ, đường 1 → 2 → 3 → 6 dài $2 + 2 + 3 = 7$, còn 1 → 4 → 5 → 6 và 1 → 2 → 5 → 6 đều dài 9.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
vector<pair<int, int>> adj[200005];
long long dist[200005];
int trace_[200005];                      // trace_[v] = đỉnh đứng ngay trước v

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for(int v = 1; v <= n; v++) dist[v] = INF;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[s] = 0; trace_[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto [v, w] : adj[u])
            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                trace_[v] = u;           // ghi nhớ: tới v tốt nhất là đi từ u
                pq.push({dist[v], v});
            }
    }
    if(dist[t] == INF){ cout << -1; return 0; }
    vector<int> path;
    for(int v = t; v != 0; v = trace_[v]) path.push_back(v);   // lần ngược từ t về s
    reverse(path.begin(), path.end());
    cout << dist[t] << "\n";
    for(int v : path) cout << v << " ";
    return 0;
}

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m, s, t = int(data[0]), int(data[1]), int(data[2]), int(data[3])
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, w = int(data[4 + 3 * i]), int(data[5 + 3 * i]), int(data[6 + 3 * i])
        adj[u].append((v, w))
        adj[v].append((u, w))
    INF = float('inf')
    dist = [INF] * (n + 1)
    trace = [0] * (n + 1)                # trace[v] = đỉnh đứng ngay trước v
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                trace[v] = u             # tới v tốt nhất là đi từ u
                heapq.heappush(pq, (dist[v], v))
    if dist[t] == INF:
        print(-1)
        return
    path, v = [], t
    while v != 0:                        # lần ngược từ t về s
        path.append(v)
        v = trace[v]
    print(dist[t])
    print(*path[::-1])

main()

Bài 3Hỏi đường nhiều lầnTrung bình

Một thành phố có $n$ nút giao ($n \le 200$) và $m$ đường một chiều, đường thứ $i$ đi từ $u_i$ tới $v_i$ mất $w_i$ phút ($1 \le w_i \le 10^6$; có thể có nhiều đường giữa cùng một cặp). Có $q$ câu hỏi ($q \le 10^5$), mỗi câu hỏi đi từ $a$ tới $b$ mất ít nhất bao nhiêu phút; in $-1$ nếu không đi được.

Input

4 5 3
1 2 5
2 3 3
1 3 10
3 4 1
4 2 2
1 3
4 3
3 1

Output

8
5
-1

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Chạy Dijkstra cho mỗi câu hỏi thì $10^5$ lần là quá nhiều; $n$ nhỏ nên tính sẵn cả bảng bằng Floyd trong $O(n^3)$ rồi trả lời mỗi câu trong $O(1)$. Nhớ lấy min khi có nhiều cạnh cùng cặp. Từ 1 tới 3: 1 → 2 → 3 mất 8 < 10. Từ 4 tới 3: 4 → 2 → 3 mất 5. Từ 3 không có đường nào quay về 1.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
long long d[505][505];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for(int i = 0; i < m; i++){
        int u, v; long long w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);               // có thể có nhiều cạnh u -> v
    }
    for(int k = 1; k <= n; k++)                  // k (đỉnh trung gian) PHẢI ở ngoài cùng
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
    while(q--){
        int u, v;
        cin >> u >> v;
        cout << (d[u][v] == INF ? -1 : d[u][v]) << "\n";
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m, q = int(data[0]), int(data[1]), int(data[2])
    INF = 10 ** 18
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    p = 3
    for _ in range(m):
        u, v, w = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]); p += 3
        d[u][v] = min(d[u][v], w)
    for k in range(n):                           # k ở ngoài cùng
        dk = d[k]
        for i in range(n):
            di = d[i]
            dik = di[k]
            if dik == INF:
                continue
            # cả hàng i được cập nhật một lần bằng list comprehension cho nhanh
            d[i] = [x if x <= dik + y else dik + y for x, y in zip(di, dk)]
    out = []
    for _ in range(q):
        u, v = int(data[p]) - 1, int(data[p + 1]) - 1; p += 2
        out.append(str(d[u][v]) if d[u][v] < INF else '-1')
    print('\n'.join(out))

main()

Bài 4Lưới chi phíTrung bình

Cho lưới $n \times m$ ($n, m \le 500$), ô $(i, j)$ có chi phí $a_{ij}$ ($0 \le a_{ij} \le 10^9$). Từ một ô được đi sang 4 ô chung cạnh. Tìm tổng chi phí nhỏ nhất của một đường đi từ ô $(1, 1)$ tới ô $(n, m)$, tính cả chi phí của ô đầu và ô cuối.

Input

3 4
1 3 1 2
1 5 1 9
4 2 1 1

Output

8

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Mỗi ô là một đỉnh, đi từ ô $x$ sang ô kề $y$ là cạnh có trọng số $a_y$ (chi phí của ô bước vào). Khởi tạo $dist[1][1] = a_{11}$ rồi chạy Dijkstra trên lưới, giống loang BFS ở bài 21 nhưng dùng hàng đợi ưu tiên. Vì được đi cả lên và sang trái nên không dùng quy hoạch động chỉ đi phải/xuống được. Ví dụ: 1 → 3 → 1 → 1 → 1 → 1 (hàng 1 sang cột 3, xuống tới hàng 3, sang cột 4) tổng 8.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
int n, m;
long long a[505][505], dist[505][505];
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){ cin >> a[i][j]; dist[i][j] = INF; }
    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;
    dist[0][0] = a[0][0];
    pq.push({dist[0][0], 0, 0});
    while(!pq.empty()){
        auto [d, r, c] = pq.top(); pq.pop();
        if(d > dist[r][c]) continue;
        for(int k = 0; k < 4; k++){
            int nr = r + dr[k], nc = c + dc[k];
            if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if(d + a[nr][nc] < dist[nr][nc]){        // bước vào ô (nr, nc) tốn a[nr][nc]
                dist[nr][nc] = d + a[nr][nc];
                pq.push({dist[nr][nc], nr, nc});
            }
        }
    }
    cout << dist[n - 1][m - 1];
    return 0;
}

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    a = list(map(int, data[2:2 + n * m]))        # ô (r, c) là a[r * m + c]
    INF = float('inf')
    dist = [INF] * (n * m)
    dist[0] = a[0]
    pq = [(a[0], 0)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        r, c = divmod(u, m)
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < n and 0 <= nc < m:
                v = nr * m + nc
                nd = d + a[v]                    # bước vào ô v tốn a[v]
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
    print(dist[n * m - 1])

main()

Bài 5Đếm số đường đi ngắn nhấtTrung bình

Cho đồ thị có hướng $n$ đỉnh, $m$ cạnh ($n, m \le 2 \cdot 10^5$, $1 \le w \le 10^9$). Nếu không đi được từ 1 tới $n$ thì in $-1$. Ngược lại in hai số: độ dài đường đi ngắn nhất từ 1 tới $n$ và số đường đi có đúng độ dài đó, lấy phần dư khi chia cho $10^9 + 7$.

Input

4 5
1 2 1
1 3 1
2 4 1
3 4 1
1 4 2

Output

2 3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Thêm mảng $cnt$ vào Dijkstra, $cnt[1] = 1$. Khi xét cạnh $u \to v$ từ đỉnh $u$ đã chốt: nếu $dist[u] + w < dist[v]$ thì đường mới tốt hơn hẳn, gán $cnt[v] = cnt[u]$; nếu bằng $dist[v]$ thì có thêm cách đi, cộng $cnt[v] \mathrel{+}= cnt[u]$. Vì $w \ge 1$ nên khi $u$ được chốt thì mọi đỉnh đứng trước nó đều đã chốt, $cnt[u]$ đã đủ. Ví dụ: ba đường dài 2 là 1 → 2 → 4, 1 → 3 → 4 và cạnh thẳng 1 → 4.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18, MOD = 1000000007;
vector<pair<int, int>> adj[200005];
long long dist[200005], cnt[200005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    for(int v = 1; v <= n; v++) dist[v] = INF;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[1] = 0; cnt[1] = 1;
    pq.push({0, 1});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto [v, w] : adj[u]){
            if(d + w < dist[v]){                 // đường mới tốt hơn hẳn
                dist[v] = d + w;
                cnt[v] = cnt[u];
                pq.push({dist[v], v});
            }
            else if(d + w == dist[v])            // thêm một cách đi cùng độ dài
                cnt[v] = (cnt[v] + cnt[u]) % MOD;
        }
    }
    if(dist[n] == INF) cout << -1;
    else cout << dist[n] << " " << cnt[n];
    return 0;
}

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    MOD = 10 ** 9 + 7
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
        adj[u].append((v, w))
    INF = float('inf')
    dist = [INF] * (n + 1)
    cnt = [0] * (n + 1)
    dist[1], cnt[1] = 0, 1
    pq = [(0, 1)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:                     # đường mới tốt hơn hẳn
                dist[v] = nd
                cnt[v] = cnt[u]
                heapq.heappush(pq, (nd, v))
            elif nd == dist[v]:                  # thêm một cách đi cùng độ dài
                cnt[v] = (cnt[v] + cnt[u]) % MOD
    print(-1 if dist[n] == INF else '%d %d' % (dist[n], cnt[n]))

main()

Bài 6Đỉnh trung tâmKhá

Có $n$ làng ($n \le 200$) nối với nhau bởi $m$ con đường hai chiều ($1 \le w \le 10^6$), giữa hai làng bất kỳ luôn có đường đi. Cần đặt trạm y tế ở một làng sao cho làng xa trạm nhất là gần nhất có thể. In số hiệu làng được chọn (nếu nhiều làng như nhau thì chọn số nhỏ nhất) và khoảng cách tới làng xa nhất đó.

Input

5 5
1 2 3
2 3 2
3 4 2
4 5 3
2 4 5

Output

3 5

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Chạy Floyd để có $d[i][j]$ cho mọi cặp. Với mỗi làng $v$, “độ lệch tâm” của nó là $\max_u d[v][u]$; chọn làng có độ lệch tâm nhỏ nhất. Trong ví dụ: đặt ở làng 3 thì xa nhất là làng 1 và làng 5, đều cách 5; đặt ở làng 2 thì làng 5 cách 7, đặt ở làng 4 thì làng 1 cách 7.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
long long d[205][205];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for(int i = 0; i < m; i++){
        int u, v; long long w;
        cin >> u >> v >> w;
        d[u][v] = d[v][u] = min(d[u][v], w);
    }
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];   // INF + INF = 2e18 vẫn vừa long long
    int best = 1; long long bestVal = INF;
    for(int v = 1; v <= n; v++){
        long long far = 0;
        for(int u = 1; u <= n; u++) far = max(far, d[v][u]);   // độ lệch tâm của v
        if(far < bestVal){ bestVal = far; best = v; }
    }
    cout << best << " " << bestVal;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    INF = 10 ** 18
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for i in range(m):
        u, v, w = int(data[2 + 3 * i]) - 1, int(data[3 + 3 * i]) - 1, int(data[4 + 3 * i])
        if w < d[u][v]:
            d[u][v] = d[v][u] = w
    for k in range(n):
        dk = d[k]
        for i in range(n):
            di = d[i]
            dik = di[k]
            if dik == INF:
                continue
            d[i] = [x if x <= dik + y else dik + y for x, y in zip(di, dk)]
    ecc = [max(row) for row in d]                # độ lệch tâm của từng làng
    best = min(range(n), key=lambda v: (ecc[v], v))
    print(best + 1, ecc[best])

main()

Bài 7Đổi hướng mũi tênKhá

Cho lưới $n \times m$ ($n, m \le 500$), mỗi ô có một mũi tên R (phải), L (trái), U (lên), D (xuống). Đứng ở một ô, em đi sang ô kề theo hướng mũi tên mà không tốn gì; muốn đi hướng khác thì phải đổi mũi tên của ô đang đứng, mỗi lần đổi tốn 1. Không được đi ra ngoài lưới. Hỏi ít nhất phải đổi bao nhiêu mũi tên để đi từ ô $(1, 1)$ tới ô $(n, m)$?

Input

3 3
RRL
LLD
URU

Output

1

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đồ thị như Hình 3: từ mỗi ô có 4 cạnh tới 4 ô kề, cạnh đúng hướng mũi tên trọng số 0, ba cạnh còn lại trọng số 1. Đây đúng là BFS 0-1 ở phần 3: cạnh 0 chen lên đầu deque, cạnh 1 xếp xuống cuối. Ví dụ: đi theo mũi tên (1, 1) → (1, 2) → (1, 3) thì mũi tên chỉ ngược về trái, đổi nó thành xuống (tốn 1), từ (2, 3) mũi tên D đưa thẳng tới đích.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int n, m;
string g[505];
int dist[505][505];
int dr[4] = {0, 0, -1, 1}, dc[4] = {1, -1, 0, 0};
string DIR = "RLUD";                             // hướng k ứng với ký tự DIR[k]

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> g[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) dist[i][j] = INT_MAX;
    deque<pair<int, int>> dq;
    dist[0][0] = 0;
    dq.push_back({0, 0});
    while(!dq.empty()){
        auto [r, c] = dq.front(); dq.pop_front();
        for(int k = 0; k < 4; k++){
            int nr = r + dr[k], nc = c + dc[k];
            if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            int w = (g[r][c] == DIR[k]) ? 0 : 1;   // đúng mũi tên: 0, đổi hướng: 1
            if(dist[r][c] + w < dist[nr][nc]){
                dist[nr][nc] = dist[r][c] + w;
                if(w == 0) dq.push_front({nr, nc});
                else dq.push_back({nr, nc});
            }
        }
    }
    cout << dist[n - 1][m - 1];
    return 0;
}

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    g = ''.join(data[2:2 + n])                   # ô (r, c) là g[r * m + c]
    INF = float('inf')
    dist = [INF] * (n * m)
    dist[0] = 0
    dq = deque([0])
    while dq:
        u = dq.popleft()
        r, c = divmod(u, m)
        for ch, nr, nc in (('R', r, c + 1), ('L', r, c - 1), ('U', r - 1, c), ('D', r + 1, c)):
            if 0 <= nr < n and 0 <= nc < m:
                v = nr * m + nc
                w = 0 if g[u] == ch else 1       # đúng mũi tên: 0, đổi hướng: 1
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    if w == 0:
                        dq.appendleft(v)
                    else:
                        dq.append(v)
    print(dist[n * m - 1])

main()

Bài 8Phát hiện chu trình âmKhá

Một sàn đổi tiền có $n$ loại tiền ($n \le 500$) và $m$ giao dịch ($m \le 5000$). Giao dịch thứ $i$ đổi từ loại $u_i$ sang loại $v_i$ với “chi phí” $w_i$ ($|w_i| \le 10^9$, có thể âm nghĩa là được lời). Nếu tồn tại một vòng giao dịch quay về loại tiền ban đầu với tổng chi phí âm (đi mãi thì lời vô hạn), in YES, ngược lại in NO. Vòng đó có thể bắt đầu ở bất kỳ loại tiền nào.

Input

4 4
1 2 1
2 3 -2
3 2 1
3 4 5

Output

YES

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đây là bài tìm chu trình âm trên đồ thị có hướng. Vì chu trình có thể nằm ở bất kỳ đâu (không cần đi tới được từ đỉnh 1), khởi tạo $dist[v] = 0$ cho mọi đỉnh (như có một nguồn ảo nối tới tất cả bằng cạnh 0), chạy Bellman–Ford $n - 1$ lượt, rồi kiểm tra lượt thứ $n$ còn nới lỏng được không. Ví dụ: vòng 2 → 3 → 2 có tổng $-2 + 1 = -1 < 0$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> eu(m), ev(m);
    vector<long long> ew(m);
    for(int i = 0; i < m; i++) cin >> eu[i] >> ev[i] >> ew[i];
    vector<long long> dist(n + 1, 0);            // nguồn ảo: mọi đỉnh bắt đầu từ 0
    bool changed = true;
    for(int round = 1; round <= n && changed; round++){   // lượt thứ n dùng để kiểm tra
        changed = false;
        for(int i = 0; i < m; i++)
            if(dist[eu[i]] + ew[i] < dist[ev[i]]){
                dist[ev[i]] = dist[eu[i]] + ew[i];
                changed = true;
            }
    }
    cout << (changed ? "YES" : "NO");            // tới lượt n vẫn còn đổi được → có chu trình âm
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    e = [(int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])) for i in range(m)]
    dist = [0] * (n + 1)                         # nguồn ảo: mọi đỉnh bắt đầu từ 0
    changed = True
    for _ in range(n):                           # lượt thứ n dùng để kiểm tra
        if not changed:
            break
        changed = False
        for u, v, w in e:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
    print('YES' if changed else 'NO')            # tới lượt n vẫn còn đổi được

main()

Bài tiếp theo · Bài 30

DSU và cây khung nhỏ nhất

Gộp các nhóm và hỏi “hai đỉnh có cùng nhóm không” gần như trong $O(1)$, rồi dùng nó để nối $n$ thành phố bằng tổng chi phí nhỏ nhất với thuật toán Kruskal.

Học bài 30 →

← Bài 28: Xâu: Hash và KMPXem cả series Thuật toán nâng cao

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!