Đường đi ngắn nhất

Mức độ: Nâng cao

BFS tìm đường đi ngắn nhất khi mọi cạnh dài như nhau. Khi các cạnh có độ dài khác nhau (đường bộ dài ngắn khác nhau, chi phí khác nhau), cần thuật toán khác. Chọn thuật toán nào phụ thuộc vào độ dài cạnh có âm không và cần khoảng cách giữa những cặp đỉnh nào.

Tình huống	Thuật toán	Số bước
mọi cạnh dài 1	BFS	n + m
cạnh dài 0 hoặc 1	BFS 0-1	n + m
cạnh không âm, từ một đỉnh	Dijkstra	khoảng m × log2n
có cạnh âm, từ một đỉnh	Bellman-Ford	n × m
mọi cặp đỉnh, n nhỏ (vài trăm)	Floyd-Warshall	n3

Dijkstra

Giữ kc[v] là độ dài đường ngắn nhất đã biết tới v. Mỗi bước lấy ra đỉnh u chưa chốt có kc nhỏ nhất và chốt nó: kc[u] chắc chắn là đáp số. Rồi thử đi tiếp qua các cạnh u → v: nếu kc[u] + w nhỏ hơn kc[v] thì cập nhật kc[v].

Vì sao chốt được? Mọi đường khác tới u đều phải đi qua một đỉnh chưa chốt v nào đó, mà kc[v] ≥ kc[u] và các cạnh không âm, nên đường đó không thể ngắn hơn kc[u]. Lý luận này sai khi có cạnh âm: đi xa hơn rồi qua cạnh âm có thể quay lại ngắn hơn.

Dùng hàng đợi ưu tiên để lấy đỉnh có kc nhỏ nhất. Mỗi lần cập nhật thì đẩy cặp (kc mới, v) vào; khi lấy ra mà kc ghi trong cặp lớn hơn kc[v] hiện tại thì đó là cặp cũ, bỏ qua.

Python

import sys
import heapq
du_lieu = sys.stdin.read().split()
n, m = int(du_lieu[0]), int(du_lieu[1])
ke = [[] for _ in range(n + 1)]
for i in range(m):
    u, v, w = int(du_lieu[2 + 3 * i]), int(du_lieu[3 + 3 * i]), int(du_lieu[4 + 3 * i])
    ke[u].append((v, w))
    ke[v].append((u, w))
VO_CUNG = float('inf')
kc = [VO_CUNG] * (n + 1)
kc[1] = 0
dong = [(0, 1)]
while dong:
    d, u = heapq.heappop(dong)
    if d > kc[u]:               # cặp cũ, u đã được chốt với kc nhỏ hơn
        continue
    for v, w in ke[u]:
        if d + w < kc[v]:
            kc[v] = d + w
            heapq.heappush(dong, (kc[v], v))
print(*[x if x < VO_CUNG else -1 for x in kc[1:]])

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, long long>>> ke(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        ke[u].push_back({v, w});
        ke[v].push_back({u, w});
    }
    const long long VO_CUNG = 4e18;
    vector<long long> kc(n + 1, VO_CUNG);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> dong;
    kc[1] = 0;
    dong.push({0, 1});
    while (!dong.empty()) {
        auto [d, u] = dong.top();
        dong.pop();
        if (d > kc[u]) continue;            // cặp cũ
        for (auto [v, w] : ke[u])
            if (d + w < kc[v]) {
                kc[v] = d + w;
                dong.push({kc[v], v});
            }
    }
    for (int u = 1; u <= n; u++) cout << (kc[u] < VO_CUNG ? kc[u] : -1) << (u < n ? ' ' : '\n');
    return 0;
}

BFS 0-1

Khi mỗi cạnh dài 0 hoặc 1 (ví dụ đi thẳng miễn phí, rẽ hoặc phá tường tốn 1), dùng deque: đi cạnh dài 0 thì đẩy đỉnh vào đầu deque, cạnh dài 1 thì đẩy vào cuối. Deque luôn chứa các đỉnh theo khoảng cách không giảm, chỉ có hai mức liền nhau, nên đây là Dijkstra mà không cần hàng đợi ưu tiên: n + m bước.

Bellman-Ford

Khi có cạnh âm (nhưng không có chu trình âm), lặp n - 1 lượt, mỗi lượt thử mọi cạnh u → v: kc[v] = min(kc[v], kc[u] + w). Đường ngắn nhất đi qua nhiều nhất n - 1 cạnh, và sau lượt thứ k thì mọi đường ngắn nhất dùng tối đa k cạnh đã được tính đúng.

Nếu ở lượt thứ n vẫn còn cạnh làm kc giảm thì có chu trình âm: đi vòng quanh nó mãi thì đường ngày càng ngắn, không có đường ngắn nhất.

Floyd-Warshall

Khoảng cách giữa mọi cặp đỉnh: kc[i][j] ban đầu là độ dài cạnh (hoặc vô cùng). Lần lượt cho phép đi qua đỉnh trung gian k = 1, 2, …, n:

kc[i][j] = min(kc[i][j], kc[i][k] + kc[k][j])

Ba vòng lặp lồng nhau, vòng k ở ngoài cùng. Sau khi xét xong k, kc[i][j] là đường ngắn nhất chỉ dùng các đỉnh trung gian trong 1, …, k. n = 400 là 6,4 × 10⁷ bước, hợp với C++; trong Python nên giữ n khoảng 150 trở xuống.

Luyện tập

Gồm 16 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Dijkstra

Bài 1. Khoảng cách từ thành phố 1

Có n thành phố, m con đường hai chiều, đường thứ i nối u, v và dài w. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra quãng đường ngắn nhất từ thành phố 1 tới các thành phố 1, 2, …, n (-1 nếu không tới được).

Ví dụ:

Nhập	In ra
5 6 1 2 4 1 3 1 3 2 2 2 4 5 3 4 8 4 5 3	0 3 1 8 11

Kiểm tra: nhập

7 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
6 5 9
4 5 6

Xem đáp số

0 7 9 20 20 11 -1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Bệnh viện gần nhất

Có n khu dân cư, m con đường hai chiều có độ dài, và k bệnh viện đặt ở k khu. Dòng đầu có n, m, k (1 ≤ k ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), dòng thứ hai có k số là các khu có bệnh viện, m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra quãng đường từ mỗi khu 1, 2, …, n tới bệnh viện gần nhất (-1 nếu không tới được bệnh viện nào).

Ví dụ:

Nhập	In ra
5 4 2 1 5 1 2 3 2 3 4 3 4 1 4 5 2	0 3 3 2 0

Kiểm tra: nhập

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

Xem đáp số

5 0 2 4 3 0 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Đi qua thành phố bắt buộc

Có n thành phố, m con đường hai chiều có độ dài. Phải đi từ thành phố 1 tới thành phố n và ghé qua thành phố k. Dòng đầu có n, m, k (2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵, 1 ≤ k ≤ n), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra quãng đường ngắn nhất, hoặc -1.

Ví dụ:

Nhập	In ra
5 6 4 1 2 2 2 5 3 1 3 1 3 4 2 4 5 6 2 4 1	7

Kiểm tra: nhập

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

Xem đáp số

16

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Đếm số đường ngắn nhất

Có n thành phố, m con đường một chiều có độ dài. Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (đường u → v, 1 ≤ w ≤ 10⁹). In ra độ dài đường ngắn nhất từ 1 tới n và số đường ngắn nhất như vậy chia lấy dư 10⁹ + 7; nếu không tới được in -1 0.

Ví dụ:

Nhập	In ra
4 5 1 2 1 1 3 2 2 4 2 3 4 1 2 3 1	3 3

Kiểm tra: nhập

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

Xem đáp số

6 2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Thành phố gặp nhau

Có n thành phố, m con đường hai chiều có độ dài (tính bằng giờ). An ở thành phố a, Bình ở thành phố b, hai bạn cùng xuất phát và muốn gặp nhau ở một thành phố nào đó. Thời gian gặp là thời gian của người đến muộn hơn. Dòng đầu có n, m, a, b (1 ≤ a, b ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w. In ra thời gian gặp nhau sớm nhất, hoặc -1.

Ví dụ:

Nhập	In ra
5 5 1 5 1 2 2 2 3 2 3 4 2 4 5 2 1 5 20	4

Kiểm tra: nhập

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

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Đường ít trạm nhất trong các đường ngắn nhất

Có n thành phố, m con đường hai chiều có độ dài. Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w. Trong các đường đi ngắn nhất từ 1 tới n, chọn đường đi qua ít con đường nhất. In ra độ dài và số con đường của nó, hoặc -1 -1 nếu không tới được.

Ví dụ:

Nhập	In ra
4 4 1 2 2 2 4 2 1 3 1 3 4 3	4 2

Kiểm tra: nhập

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

Xem đáp số

3 2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Dijkstra trên trạng thái và biến thể

Bài 7. Một phiếu giảm giá

Có n thành phố, m chuyến bay một chiều, chuyến thứ i bay từ u tới v giá w. Bạn có một phiếu giảm giá, dùng cho đúng một chuyến bay thì giá chuyến đó còn một nửa (làm tròn xuống). Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra tổng giá ít nhất để bay từ 1 tới n, hoặc -1.

Ví dụ:

Nhập	In ra
3 4 1 2 3 2 3 1 1 3 7 2 1 5	2

Kiểm tra: nhập

5 7
1 2 10
2 5 10
1 3 3
3 4 3
4 5 9
1 5 30
3 5 25

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Đường rộng nhất

Có n thành phố, m con đường hai chiều, đường thứ i có tải trọng tối đa c (xe nặng hơn c không đi qua được). Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, c (1 ≤ c ≤ 10⁹). In ra khối lượng lớn nhất của một chiếc xe đi được từ 1 tới n, hoặc 0 nếu không có đường.

Ví dụ:

Nhập	In ra
4 5 1 2 5 2 4 3 1 3 4 3 4 6 2 3 8	5

Kiểm tra: nhập

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

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Đường ngắn thứ hai

Có n thành phố, m con đường hai chiều có độ dài. Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁶). Đường đi được phép quay lại thành phố cũ và đi lại con đường cũ. In ra độ dài đường đi ngắn thứ hai từ 1 tới n: nhỏ nhất trong các độ dài lớn hơn hẳn độ dài ngắn nhất. Nếu không có, in -1.

Ví dụ:

Nhập	In ra
4 4 1 2 100 2 4 200 2 3 250 3 4 100	450

Kiểm tra: nhập

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

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Đường chi phí nhỏ nhất trên bảng

Bảng h hàng, w cột, ô (r, c) có chi phí a_rc khi bước vào (ô xuất phát cũng tính). Đi từ ô trên cùng bên trái tới ô dưới cùng bên phải, mỗi bước sang ô chung cạnh (được đi cả bốn hướng). Dòng đầu có h, w (1 ≤ h, w ≤ 500), h dòng sau mỗi dòng có w số (0 ≤ a_rc ≤ 10⁶). In ra tổng chi phí nhỏ nhất.

Ví dụ:

Nhập	In ra
3 3 1 9 1 1 9 1 1 1 1	5

Kiểm tra: nhập

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

Xem đáp số

25

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. BFS 0-1

Bài 11. Phá ít tường nhất

Mê cung h hàng, w cột gồm . và #. Đi từ ô trên cùng bên trái tới ô dưới cùng bên phải (cả hai là .), mỗi bước sang ô chung cạnh; bước vào ô # thì phải phá bức tường đó. Dòng đầu có h, w (1 ≤ h, w ≤ 1000), h dòng sau là mê cung. In ra số bức tường ít nhất phải phá.

Ví dụ:

Nhập	In ra
3 4 .#.. ##.# ....	1

Kiểm tra: nhập

5 6
.##...
.#.##.
.#.#..
##.#.#
...#..

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Sửa mũi tên

Bảng h hàng, w cột, mỗi ô ghi một mũi tên R, L, D, U (phải, trái, xuống, lên). Đứng ở một ô thì đi theo mũi tên của ô đó sang ô kề miễn phí; muốn đi hướng khác thì phải sửa mũi tên của ô đó, tốn 1. Dòng đầu có h, w (1 ≤ h, w ≤ 500), h dòng sau mỗi dòng là w ký tự. In ra số lần sửa ít nhất để đi từ ô trên cùng bên trái tới ô dưới cùng bên phải.

Ví dụ:

Nhập	In ra
3 3 RRD ULD LLR	0

Kiểm tra: nhập

4 4
RRRR
LLLL
RRRR
LLLL

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Cạnh âm và mọi cặp đỉnh

Bài 13. Cạnh âm

Đồ thị có hướng n đỉnh, m cạnh, cạnh có thể có độ dài âm; đề bảo đảm không có chu trình âm. Dòng đầu có n, m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 3000), m dòng sau mỗi dòng có u, v, w (|w| ≤ 10⁶). In ra độ dài đường ngắn nhất từ đỉnh 1 tới các đỉnh 1, 2, …, n (INF nếu không tới được).

Ví dụ:

Nhập	In ra
4 5 1 2 4 1 3 2 3 2 -3 2 4 1 3 4 5	0 -1 2 0

Kiểm tra: nhập

6 8
1 2 6
1 3 7
2 4 5
3 4 -3
4 2 -2
2 5 -4
3 6 9
5 6 7

Xem đáp số

0 2 7 4 -2 5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Có chu trình âm không

Đồ thị có hướng n đỉnh, m cạnh, độ dài có thể âm. Dòng đầu có n, m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 3000), m dòng sau mỗi dòng có u, v, w (|w| ≤ 10⁶). In ra YES nếu đồ thị có một chu trình mà tổng độ dài các cạnh âm, ngược lại NO.

Ví dụ:

Nhập	In ra
3 3 1 2 1 2 3 -2 3 1 0	YES

Kiểm tra: nhập

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

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Hỏi khoảng cách giữa hai thành phố

Có n thành phố, m con đường hai chiều có độ dài, và q câu hỏi. Dòng đầu có n, m, q (1 ≤ n ≤ 300, 0 ≤ m ≤ n × n, 1 ≤ q ≤ 10⁵), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹), q dòng sau mỗi dòng có a, b. Với mỗi câu hỏi, in ra quãng đường ngắn nhất từ a tới b, hoặc -1.

Ví dụ:

Nhập	In ra
4 4 3 1 2 5 2 3 1 3 4 2 1 4 10 1 4 2 4 4 1	8 3 8

Kiểm tra: nhập

5 6 4
1 2 2
2 3 2
3 4 2
4 5 2
1 5 20
2 5 3
1 5
3 5
1 1
4 2

Xem đáp số

5
4
0
4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Thành phố trung tâm

Có n thành phố, m con đường hai chiều có độ dài, mọi thành phố đi được tới nhau. Chọn một thành phố làm trung tâm sao cho quãng đường từ trung tâm tới thành phố xa nhất là nhỏ nhất. Dòng đầu có n, m (1 ≤ n ≤ 300, n - 1 ≤ m ≤ n × n), m dòng sau mỗi dòng có u, v, w. In ra thành phố được chọn (nếu nhiều, số nhỏ nhất) và quãng đường tới thành phố xa nhất.

Ví dụ:

Nhập	In ra
4 4 1 2 3 2 3 3 3 4 3 4 1 10	2 6

Kiểm tra: nhập

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

Xem đáp số

3 6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.