¶ Các thuật toán tìm đường đi ngắn nhất - Phần 2 - Chu trình âm
Tác giả:
- Trần Hoài An - THPT Hoàng Lê Kha, Tây Ninh
- Nguyễn Đức Kiên - Đại học Công nghệ - ĐHQGHN
Reviewer:
- Nguyễn Xuân Tùng - Đại học Quốc Tế, Đại học Quốc gia Thành phố Hồ Chí Minh
Chuỗi bài viết: Phần 1 • Phần 2 • Phần 3
¶ Giới thiệu
Tiếp tục phần 1, trong bài viết này, ta sẽ đi sâu vào hai thuật toán tiếp theo:
- Thuật toán Bellman - Ford.
- Thuật toán Floyd-Warshall (còn gọi là thuật toán Floyd).
Khác với hai thuật toán bài trước, hai thuật toán này có thể giúp tìm được "chu trình âm" của đồ thị. Do vậy, chúng ta hãy đi đến khái niệm này đầu tiên.
¶ Khái niệm về chu trình âm
- Chu trình âm là một chu trình trong đó tổng trọng số các cạnh là số âm. Ví dụ trong hình dưới, ta có một chu trình âm có tổng trọng số là
- Nếu trên đường đi từ đến chứa chu trình âm thì độ dài đường đi ngắn nhất từ đến sẽ là . Vì vậy nên sự xuất hiện của chu trình âm trong đồ thị sẽ khiến một số cặp đỉnh không tồn tại đường đi ngắn nhất (chỉ tồn tại đường đi có độ dài âm vô cực).
- Ví dụ: Ở đồ thị trên, đường đi ngắn nhất từ đến sẽ có cách đi là vô hạn lần qua chu trình âm đã nhắc đến, sau đó mới đi đến . Như vậy không có đường đi ngắn nhất.
¶ Thuật toán Bellman - Ford
Thuật toán Bellman-Ford dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path), đồ thị có thể có trọng số âm.
¶ Bài toán
Cho đồ thị có hướng gồm đỉnh, cạnh và một đỉnh nguồn . Mỗi cạnh có trọng số nguyên (có thể âm, dương, hoặc bằng ). Yêu cầu xác định đường đi ngắn nhất từ đỉnh nguồn đến mỗi đỉnh từ đến , với kết quả được xuất như sau:
- Nếu không tồn tại đường đi từ đến , in ra Impossible.
- Nếu tồn tại đường đi từ đến nhưng không có đường đi ngắn nhất (do chu trình âm), in ra -Infinity.
- Trong các trường hợp khác, in ra độ dài đường đi ngắn nhất từ đến .
Input:
- Dòng đầu tiên gồm ba số nguyên .
- dòng tiếp theo, mỗi dòng gồm ba số nguyên đại diện cho một cạnh có hướng từ đến với trọng số .
Output:
- Gồm dòng, mỗi dòng là kết quả đường đi ngắn nhất từ đến các đỉnh từ đến .
Ràng buộc:
- , :
Sample Input
7 6 4
0 1 7
2 0 1
1 2 -9
2 5 1000
3 0 7
4 3 3
Sample Output
-Infinity
-Infinity
-Infinity
3
0
-Infinity
Impossible
¶ Ý tưởng của thuật toán.
Xét trường hợp đơn giản hơn, khi đồ thị không có trọng số âm (tức đường đi ngắn nhất luôn tồn tại).
Thuật toán Bellman-Ford sẽ thực hiện nhiều bước lặp. Ở mỗi bước lặp, ta sẽ duyệt tất cả các cạnh trên đồ thị, so sánh đường đi đã tìm được với đường đi
- Ví dụ đồ thị sau:
- Giả sử ta tìm được đường đi từ có độ dài là , và đường đi từ có độ dài là . Như vậy ta có thể sử dụng cạnh để nối dài đường đi thành có độ dài bằng , tốt hơn đường đi trực tiếp ta đã tìm được.
Nhận xét: Vòng lặp trên cần thực hiện lần, mỗi lần đi qua toàn bộ cạnh, là sẽ đủ để tìm đường đi ngắn nhất.
Chứng minh
Nhận xét rằng một đường đi ngắn nhất bất kì sẽ không có đỉnh nào được đi lại quá một lần. Như vậy một đường đi ngắn nhất sẽ không có quá cạnh. Việc thực hiện phép tính cũng đồng nghĩa với thêm một cạnh vào hành trình đi từ đến . Vậy một chỉ có thể được tối ưu tối đa lần, và từ lần thứ trở đi sẽ không thể tối ưu hơn được nữa.
¶ Cài đặt
Ở thuật toán này, đồ thị thường được lưu ở dạng danh sách cạnh.
- Định nghĩa là trọng số cạnh nối từ đỉnh đến đỉnh (nếu có).
- Định nghĩa mảng là đường đi ngắn nhất từ .
Ban đầu, chưa có đường đi nào:- với mọi khác
- Nếu cần tìm lại chính đường đi ngắn nhất, ta định nghĩa thêm mảng truy vết . Ta gán với ý nghĩa là đường đi ngắn nhất từ cần đi qua cạnh .
Ban đầu mọi bằng nghĩa là chưa có đường đi. - Thực hiện lần:
Xét lần lượt các cạnh trong đồ thị.
Nếu , cập nhật:- .
- Độ phức tạp: Có tổng cộng lần lặp, mỗi lần lặp cần duyệt tất cả cạnh trong đồ thị, như vậy độ phức tạp của thuật toán là .
Code:
const long long INF = 2000000000000000000LL;
struct Edge {
int u, v;
long long w; // cạnh từ u đến v, trọng số w
};
void bellmanFord(int n, int S, vector<Edge> &e,
vector<long long> &D, vector<int> &trace) {
// e: danh sách cạnh
// n: số đỉnh
// S: đỉnh bắt đầu
// D: độ dài đường đi ngắn nhất
// trace: mảng truy vết đường đi
// INF nếu không có đường đi
// -INF nếu có đường đi âm vô tận
D.resize(n, INF);
trace.resize(n, -1);
D[S] = 0;
for(int T = 1; T < n; T++) {
for (auto E : e) {
int u = E.u;
int v = E.v;
long long w = E.w;
if (D[u] != INF && D[v] > D[u] + w) {
D[v] = D[u] + w;
trace[v] = u;
}
}
}
}
¶ Tìm lại đường đi ngắn nhất
Thao tác tìm đường đi ngắn nhất từ đến khá đơn giản, ta sẽ bắt đầu từ đỉnh , sau đó truy vết theo mảng ngược về .
vector<int> trace_path(vector<int> &trace, int S, int u) {
if (u != S && trace[u] == -1) return vector<int>(0); // không có đường đi
vector<int> path;
while (u != -1) { // truy vết ngược từ u về S
path.push_back(u);
u = trace[u];
}
reverse(path.begin(), path.end()); // cần reverse vì đường đi lúc này là từ u về S
return path;
}
¶ Tìm chu trình âm
Thuật toán Bellman-Ford có thể xử lí được thêm trường hợp nhận biết chu trình âm, cũng như nhận biết nếu không tồn tại đường đi ngắn nhất đến một đỉnh.
¶ Nhận biết đường đi âm vô cực
- Nhận xét tiếp rằng, ta có thể chạy vòng quanh chu trình âm liên tục để được đường đi ngắn hơn. Như vậy thuật toán Bellman-Ford ở vòng lặp thứ trở đi vẫn sẽ liên tục tối ưu được đường đi, thay vì dừng lại ở lần thứ .
- Ta chỉ cần chạy thuật toán Bellman-Ford thêm một lần nữa, những đỉnh nào vẫn còn tối ưu được ở lần chạy thứ hai sẽ tối ưu được mãi mãi, và đó là các đỉnh không tồn tại đường đi ngắn nhất.
Code:
// sau khi chạy xong N-1 vòng lặp Bellman-Ford
for(int T = 0; T < n; T++){
for (auto E : e) {
int u = E.u;
int v = E.v;
long long w = E.w;
if (D[u] != INF && D[v] > D[u] + w) {
// vẫn còn tối ưu được --> âm vô cực
D[v] = -INF;
trace[v] = u;
}
}
}
¶ Tìm chu trình âm
Một số bài toán có thể yêu cầu ta tìm một chu trình âm bất kì trong đồ thị. Ta có thể chỉnh sửa thuật toán Bellman-Ford lại như sau:
-
Thay vì chạy vòng lặp Bellman-Ford như trường hợp trên, ta chỉ cần chạy một vòng lặp. Như vậy là đủ để phát hiện ít nhất một đỉnh có đường đi bằng (nếu có).
-
Tiến hành truy vết: Bắt đầu từ đỉnh bất kì có đường đi bằng , ta sẽ truy vết theo mảng :
- Trước hết gán đủ lần để chắc chắn thuộc chu trình âm nào đó.
Giải thích
Ban đầu có thể đỉnh có đường đi bằng nhưng chưa chắc thuộc chu trình âm. Ví dụ trường hợp sau:
Ở đây, từ đến có độ dài đường đi ngắn nhất bằng , tuy nhiên đỉnh lại không thuộc chu trình âm nào.- Sau đó, sẽ thuộc một chu trình âm. Ta chỉ cần truy vết đỉnh theo mảng cho đến khi gặp lại chính nó, sẽ được một chu trình.
-
Chu trình vừa truy vết chính là một chu trình âm của đồ thị. Lưu ý ta vẫn phải đảo ngược kết quả truy vết, vì ta đang truy vết ngược so với đồ thị gốc.
bool findNegativeCycle(int n, vector<Edge> &e, vector<long long> &D,
vector<int> &trace, vector<int> &negCycle) {
// mảng D và trace đã được chạy qua thuật toán Bellman-Ford
int negStart = -1; // đỉnh bắt đầu
for (auto E : e) {
int u = E.u;
int v = E.v;
long long w = E.w;
if (D[u] != INF && D[v] > D[u] + w) {
trace[v] = u;
negStart = v; // đã tìm thấy -INF
break;
}
}
if (negStart == -1) return false; // không có chu trình âm
int u = negStart;
for (int i = 0; i < n; i++) {
u = trace[u]; // đưa u về chu trình âm
}
negCycle = vector<int>(1, u);
for (int v = trace[u]; v != u; v = trace[v]) {
negCycle.push_back(v); // truy vết một vòng
}
reverse(negCycle.begin(), negCycle.end());
return true;
}
¶ Thuật toán Floyd-Warshall
Thuật toán Floyd-Warshall dùng để giải quyết bài toán đường đi ngắn nhất mọi cặp đỉnh (All-pairs shortest path), đồ thị có thể có trọng số âm.
¶ Bài toán
Cho đồ thị gồm đỉnh và một ma trận trọng số , trong đó ô cho biết rằng có một đường đi trực tiếp từ với trọng số là . Yêu cầu tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị.
Input:
- Dòng đầu tiên gồm số nguyên dương .
- dòng tiếp theo, mỗi dòng gồm số biểu diễn một ma trận trong đó ô cho biết đường đi trực tiếp từ có trọng số là .
Output:
- Ma trận kết quả trong đó giá trị ô là đường đi ngắn nhất từ .
Ràng buộc:
Sample Input
5
0 4 2 1 6
7 0 1 2 4
2 3 0 1 2
4 5 5 0 1
6 8 7 3 0
Sample Output
0 4 2 1 2
3 0 1 2 3
2 3 0 1 2
4 5 5 0 1
6 8 7 3 0
¶ Ý tưởng của thuật toán.
Ý tưởng của thuật toán này là: "Liệu chúng ta có thể chèn một đỉnh vào đường đi ngắn nhất giữa 2 đỉnh và ?".
- Ví dụ như có một đường đi ngắn nhất từ như sau: . Vậy việc tính đường đi ngắn nhất từ hoàn toàn có thể được chia thành tính đường đi ngắn nhất từ sau đó cộng với đường đi ngắn nhất từ . Tương tự thế đường đi ngắn nhất từ và lại tiếp tực được phân hoạch thành những đường đi ngắn nhất khác đơn giản hơn và tối ưu hơn.
Ta nhận thấy có một cấu trúc đệ quy, chia nhỏ bài toán ở đây. Ý tưởng này cho phép chúng ta thực hiện một thuật toán mang hương vị quy hoạch động như sau:
- Gọi là đường đi ngắn nhất, trong đó ta chỉ được đi qua đỉnh đầu tiên (có số thứ tự từ đến ), ngoại trừ chính và . Ta có công thức truy hồi:
- (không được dùng đỉnh nào ngoài chính ).
- min của 2 trường hợp:
- : ta không dùng đỉnh làm trung gian, giữ nguyên đường đi cũ.
- : ta dùng đỉnh làm trung gian, từ đường đi thành đường đi .
Đến đây ta có thể sử dụng trực tiếp công thức quy hoạch động để cài đặt thuật toán.
Để ý rằng, với mọi giá trị , chỉ phụ thuộc vào . Hơn nữa, với như trên, luôn tối ưu hơn . Vì vậy, ta hoàn toàn có thể bỏ trạng thái thứ ba của công thức quy hoạch động, và viết lại công thức như sau: $$D(u, v) = \min(D(u, v), D(u, k) + D(k, v))$$
¶ Cài đặt
-
Định nghĩa:
- là giá trị đường đi trực tiếp từ .
- là giá trị đường đi ngắn nhất từ .
- là mảng truy vết đường đi ngắn nhất từ
-
Đồ thị sẽ được lưu dưới dạng ma trận kề. Ban đầu sẽ khởi tạo mọi vì khi chưa tối ưu gì thì đường đi trực tiếp luôn là đường đi ngắn nhất.
- sẽ khởi tạo bằng với mọi cặp .
- Nếu không có cạnh nối giữa và , coi như .
-
Thuật toán chỉ cần một vòng lặp xét mọi đỉnh như một đỉnh trung gian. Tiếp theo đến là 2 vòng lặp , , có ý nghĩa thử chèn đỉnh vào giữa đường đi từ đến .
- Nếu như được tối ưu bằng đỉnh , ta cập nhật thêm
-
Độ phức tạp của thuật toán là .
Chú ý: Thuật toán Floyd-Warshall có thứ tự 3 vòng lặp là thay vì (đỉnh trung gian phải được đặt ở vòng lặp ngoài cùng), đây là một nhầm lẫn tương đối phổ biến khi cài đặt.
Code mẫu bằng C++:
Thuật toán có thể được cài đặt rất dễ dàng chỉ với 3 vòng lặp:
void init_trace(vector<vector<int>> &trace) {
int n = trace.size();
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
trace[u][v] = u;
}
}
}
void floydWarshall(int n, vector<vector<long long>> &w, vector<vector<long long>> &D, vector<vector<int>> &trace) {
D = w;
init_trace(trace); // nếu cần dò đường đi
for (int k = 0; k < n; k++) {
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (D[u][v] > D[u][k] + D[k][v]) {
D[u][v] = D[u][k] + D[k][v];
trace[u][v] = trace[k][v];
}
}
}
}
}
¶ Tìm lại đường đi ngắn nhất
Giống như hai thuật toán Bellman-Ford và Dijkstra, để tìm đường đi từ đến , ta sẽ bắt đầu từ , truy ngược về theo mảng trace đã tìm được.
vector<int> trace_path(vector<vector<int>> &trace, int u, int v) {
vector<int> path;
while (v != u) { // truy vết ngược từ v về u
path.push_back(v);
v = trace[u][v];
}
path.push_back(u);
reverse(path.begin(), path.end()); // cần reverse vì đường đi từ v ngược về u
return path;
}
¶ Trường hợp chu trình âm
Khi đồ thị có chu trình âm, dễ thấy cũng sẽ bị "tối ưu hoá" và sẽ nhận giá trị âm. Đây là cơ sở để ta nhận biết đồ thị có chu trình âm hay không.
Muốn kiểm tra xem đồ thị có chu trình âm hay không, ta chỉ cần chỉ ra một đỉnh sao cho . Còn để tìm một chu trình âm bất kỳ, ta truy vết như bình thường với đường đi là từ đến .
Nếu bài toán chỉ yêu cầu kiểm tra xem đồ thị có chu trình âm hay không hoặc chỉ ra một chu trình âm bất kỳ của đồ thị, thuật toán Bellman-Ford sẽ tốt hơn. Nhưng nếu đây là một yêu cầu đi kèm của bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh, ta vẫn có thể áp dụng thuật toán Floyd để thực hiện nó.
¶ Tổng kết
Sau đây là bảng so sánh các thuật toán đã được đề cập:
| Thuật toán | Bài toán | Độ phức tạp | Sử dụng được trọng số âm | Tìm được chu trình âm |
|---|---|---|---|---|
| DP theo thứ tự topo | Một nguồn | Có | Yêu cầu thuật toán: Đồ thị không chu trình | |
| Dijkstra | Một nguồn | Không | Không | |
| Dijkstra + Min Heap | Một nguồn | Không | Không | |
| Bellman-Ford | Một nguồn | Có | Có | |
| Floyd-Warshall | Mọi cặp đỉnh | Có | Có |
Trong trường hợp có chu trình âm, thuật toán Floyd-Warshall có thể phải tính toán đến những giá trị rất nhỏ (về phía số âm), đủ để gây ra hiện tượng tràn số (thậm chí với tương đối nhỏ). Cần phải chú ý đặc biệt đến trường hợp này khi cài đặt. Một cách thường dùng để giải quyết trường hợp này là gán D[u][v] = max(D[u][v], -INF) ngay sau mỗi lần tối ưu, chặn không cho xuống dưới hằng số âm vô tận.
Với đồ thị thưa, không có trọng số âm, thay vì sử dụng thuật toán Floyd, ta có thể chạy thuật toán Dijkstra cải tiến lần với đỉnh nguồn để tìm đường đi ngắn nhất giữa mọi cặp đỉnh, với độ phức tạp .
Phần 3 của bài viết sẽ tiếp tục giới thiệu với bạn đọc một biến thể của thuật toán Bellman-Ford, hiệu quả đến mức người ta gọi nó là "Shortest Path Faster algorithm". Mời bạn đọc tiếp tục theo dõi.
¶ Bài tập vận dụng
Thuật toán Bellman-Ford:
- Kattis - shortestpath3
- CSES - High Score
- CSES - Cycle Finding (tìm chu trình âm)
- Kattis - xyzzy
Thuật toán Floyd-Warshall:
- CSES - Shortest Route II (trọng số không âm)
- Kattis - allpairspath (trọng số có thể âm)
- Codeforces - Greg and Graph
- Các bài theo tag trên VNOJ