Bellman-Ford – Đồ thị (Graph) Phần 7: Các thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số (Phần 3)

Đỗ Thị Hồng Ngát 14/11/2023
14
Th11

Đồ thị (Graph) Phần 7: Các thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số (Phần 3) – Bellman-Ford

1. Giới thiệu

Bài viết này đề cập về thuật toán Bellman-Ford. Bài toán tìm đường đi ngắn nhất trên đồ thị là một trong những bài toán đa dạng, có nhiều ứng dụng thực tế ví dụ như Google Maps. Các dạng bài về tìm đường đi ngắn nhất cũng thường xuyên có mặt trong các kì thi lập trình thi đấu.

2. Bài toán

Cho đồ thị có hướng \(N\) đỉnh và \(M\) cạnh, và một đỉnh nguồn là đỉnh \(S\). Mỗi cạnh có trọng số nguyên. Trọng số này có thể âm hoặc dương hoặc bằng 0. Với mỗi đỉnh \(u\) từ \(1\) đến \(N\). Yêu cầu xuất kết quả tại mỗi đỉnh \(u\) như sau:

  1. Nếu không tồn tại đường đi từ \(S\) đến \(u\) thì in ra: \(Impossible\)
  2. Nếu tồn tại đường đi từ \(S\) đến \(u\) nhưng không có đường đi ngắn nhất in ra: \(-Infinity\)
  3. Trường hợp còn lại in ra đường đi ngắn nhất từ \(S\) đến \(u\).

Input: Dòng đầu tiên gồm 3 số nguyên \(N, M, S\). \(M\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(u, v, W\) biểu diễn một cạnh một chiều từ \(u\) đến \(v\) với trọng số là \(W\).

Output: gồm \(N\) dòng cho biết đường đi ngắn nhất từ đỉnh \(S\) đến các đỉnh từ \(1\) đến \(N\)

Giới hạn bài toán : \(N <= 1000, M <= 5000\)

Sample Input

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

Sample Output

-Infinity
-Infinity
-Infinity
3
0
-Infinity
Impossible

Bellman-Ford

3. Khái niệm 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 bài toán trên, ta có một chu trình âm \(1 – 2 – 3 – 1\) có tổng trọng số là \(7 – 9 + 1 = -1\). Nếu trên đường đi từ \(u\) đến \(v\) chứa chu trình âm thì độ dài đường đi ngắn nhất từ u đến v sẽ là âm vô cực. Vì vậy nên một số cặp đỉnh không tồn tại đường đi ngắn nhất do có chu trình âm trên đường đi giữa chúng (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ừ \(4\) đến \(6\) sẽ có cách đi là vô hạn lần qua chu trình âm đã nhắc đến, sau đó mới đi đến \(6\). Như vậy không có đường đi ngắn nhất.

4. Ý 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 là đường đi ngắn nhất luôn tồn tại). Ở mỗi vòng lặp, ta duyệt qua tất cả cạnh \((u,v)\), so sánh đường đi từ \(S->v\) đã tìm được với đường đi \(S->u->v\)

Ví dụ đồ thị sau: ta tìm được đường đi từ \(1->3\) có độ dài là \(4\), và đường đi từ \(1->2\) độ dài là \(2\). Như vậy ta có thể sử dụng cạnh \((2,3)\) để nối dài đường đi \(1->2\) thành \(1->2->3\) có độ dài bằng \(3\), ngắn hơn đường đi trực tiếp ta đã tìm được.

Có thể chứng minh được rằng, vòng lặp trên cần thực hiện \(N−1\) lần, mỗi lần đi qua toàn bộ \(M\) cạnh, là sẽ đủ để tìm đường đi ngắn nhất. 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á \(N−1\) cạnh. Việc thực hiện phép tính \(D_{v}=D_{u}+W_{u,v}\) cũng đồng nghĩa với thêm một cạnh \(u -> v\) vào hành trình đi từ \(s\) đến \(v\). Vậy mỗi \(D_{u}\) chỉ có thể được tối ưu tối đa \(N-1\) lần, và từ lần thứ \(N\) trở đi sẽ không thể tối ưu hơn được nữa.

Cài đặt

  • Định nghĩa \(W_{u,v}\) là trọng số cạnh nối từ đỉnh \(u\) đến đỉnh \(v\).
  • Định nghĩa mảng \(D[u][v]\) là đường đi ngắn nhất từ đỉnh \(u\) đến đỉnh \(v\), mảng truy vết \(trace[u]\).
  • Thực hiện \(N-1\) lần: Duyệt qua tất cả cạnh \((u,v)\). Nếu \(D[u] + W_{u,v} < D[v]\) thì cập nhật \(D[v] = D[u] + W_{u,v}\) và \(trace[u] = v\).
  • Độ phức tạp: \(O(N*M)\) do ta lặp \(N-1\) lần, mỗi lần ta xử lý tất cả cạnh trong đồ thị.

Code

#define fi first
#define se second
#define int long long
#define pii pair<int,int>
const int inf = 1e18;
const int mx = 1e6 + 5;
vector<pair<int,pii>> edges;
int D[mx], trace[mx];
void BellmanFord(){
	for (int i = 1; i <= n; i++){
		D[i] = inf;
		trace[i] = -1;
	}
	D[s] = 0;
	for (int i = 1; i < n; i++){
		for (auto x : edges){
			int w = x.fi;
			int u = x.se.fi;
			int v = x.se.se;
			if (D[u] != inf && D[u] + w < D[v]){
				D[v] = D[u] + w;
				trace[v] = u;
			}
		}
	}
}

Truy vết đường đi ngắn nhất

Ta sẽ bắt đầu từ đỉnh \(u\), sau đó truy vết theo mảng trace ngược về S.

vector<int> path; // vector lưu đường đi từ S đến u.
void truyvet() {
    if (u != S && trace[u] == -1) return;
    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
}

5. Các trường hợp có chu trình âm

Tại sao thuật toán Dijkstra không làm với đồ thị có trọng số âm?

Đồ thị có trọng số âm có thể chứa chu trình âm, do đó đường đi ngắn nhất giữa một số cặp đỉnh sẽ là \(-infinity\). Thuật toán Dijkstra không có khả năng nhận biết chu trình âm, do đó thuật toán sẽ lặp vô hạn để tối ưu đường đi với chu trình đó.

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ứ \(N\) trở đi vẫn sẽ liên tục tối ưu được đường đi, thay vì dừng lại ở lần thứ \(N-1\). Ta chỉ cần chạy thuật toán Bellman-Ford thêm một lần nữa với \(N\) vòng lặp, 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:

#define fi first
#define se second
#define int long long
#define pii pair<int,int>
const int inf = 1e18;
const int mx = 1e6 + 5;
vector<pair<int,pii>> edges;
int D[mx], trace[mx];
void BellmanFord(){
	for (int i = 1; i <= n; i++){
		D[i] = inf;
		trace[i] = -1;
	}
	D[s] = 0;
	for (int i = 1; i < n; i++){
		for (auto x : edges){
			int w = x.fi;
			int u = x.se.fi;
			int v = x.se.se;
			if (D[u] != inf && D[u] + w < D[v]){
				D[v] = D[u] + w;
				trace[v] = u;
			}
		}
	}
	for (int i = 1; i <= n; i++){
		for (auto x : edges){
			int w = x.fi;
			int u = x.se.fi;
			int v = x.se.se;
			if (D[u] != inf && D[u] + w < D[v]){
				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 \(N\) 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 \(infinity\) (nếu có).
  • Tiến hành truy vết: Bắt đầu từ đỉnh \(u\) bất kì có đường đi bằng \(infinity\), ta sẽ truy vết theo mảng \(trace\): Trước hết gán \(u = trace[u]\) đủ \(N\) lần. Mục đích của bước này là để \(u\) chắc chắn thuộc chu trình âm. Ban đầu có thể đỉnh \(u\) có đường đi bằng \(infinity\) nhưng chưa chắc thuộc chu trình âm. Sau đó, \(u\) sẽ thuộc một chu trình âm. Ta chỉ cần truy vết đỉnh \(u\) theo mảng \(trace\) 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.

Code:

vector<int> negcycle;
void findnegcycle() {
    int start = -1;
    for (auto x : edges) {
        int w = x.fi;
        int u = x.se.fi;
        int v = x.se.se;
        if (D[u] != inf && D[v] > D[u] + w) {
            D[v] = -inf;
            trace[v] = u;
            start = v;
        }
    }

    if (start == -1) return; // không có chu trình âm
    for (int i = 1; i <= n; i++) {
        start = trace[start]; // đưa start về chu trình âm
    }
    negcycle.push_back(start);
    while(1){
    	int v = trace[start];
    	if (v==start) break;
    	negcycle.push_back(v); 
    	// truy vết một vòng
    }
    reverse(negcycle.begin(), negcycle.end());
}

6. So sánh Bellman-Ford với các thuật toán tìm đường đi ngắn nhất khác

Ta có bảng so sánh:

Tên thuật toán Độ phức tạp Sử dụng cho trọng số âm Tìm chu trình âm
Dijkstra \(O(M*logN)\) Không Không
FloyD-Warshall \(O(N^{3})\) Không Không
Bellman-Ford \(O(M*N)\) Có Có

7. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn
Unable to display PDF file. Download instead.

ÁP DỤNG GIẢI BÀI TOÁN SCHOOL:

Nhận xét:

  • Để tìm đường đi ngắn nhất cho bài này, ta có thể sử dụng Bellman-Ford (không có chu trình âm).

Code mẫu:

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define pii pair<int,int>
const int inf = 1e18;
const int mx = 1e6 + 5;
vector<pair<int,pii>> edges;
int D[mx];
int n,m;
void BellmanFord(){
	for (int i = 1; i <= n; i++){
		D[i] = inf;
	}
	D[1] = 0;
	for (int i = 1; i < n; i++){
		for (auto x : edges){
			int w = x.fi;
			int u = x.se.fi;
			int v = x.se.se;
			if (D[u] != inf && D[u] + w < D[v]){
				D[v] = D[u] + w;
			}
		}
	}
}
void sub(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int k, u, v, l; cin >> k >> u >> v >> l;
		if (k == 1) {
			edges.push_back({l, {u,v}});
			// tồn tại đường đi 1 chiều từ u tới v có độ dài l
		}
		else {
			edges.push_back({l, {u,v}});
			edges.push_back({l, {v,u}});
			// tồn tại đường đi 2 chiều từ u tới v
		}
	}
	BellmanFord();
	cout << D[n];
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	sub();
	return 0;
}
//honguwu

Bài tập vận dụng khác:

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *