Tìm kiếm đường đi ngắn nhất trên đồ thị (Bellman-Ford)

Dẫn nhập

Trong bài học trước, chúng ta đã cùng nhau đi tìm hiểu về thuật toán Floyd-Warshall trong tìm kiếm đường đi ngắn nhất trên đồ thị. Hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một thuật toán có thể coi là thuật toán phổ biến nhất trong tìm kiếm đường đi ngắn nhất. Để biết cụ thể, hãy cùng nhau bắt đầu bài học nào!

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Các kiến thức cần thiết để theo dõi khóa học
• Đồ thị và cây
• BFS và DFS
• Priority Queue
• Thuật toán Floyd-Warshall
• Thuật toán Dijkstra 

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Chu trình âm

• Thuật toán Bellman-Ford

Chu trình âm

Khái niệm

Ta có một đồ thị như sau:

Bài toán đặt ra ở đây là tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại.

Nhìn vào đồ thị trên, ta thấy có một điểm khác hơn so với các đồ thị ở những bài học trước đó là cạnh nối đỉnh 4 và đỉnh 5 có trọng số là một số âm. Vậy thì điều này ảnh hưởng gì đến bài toán?

Hãy cùng thử sử dụng thuật toán Dijkstra lên đồ thị trên nhé:

• Đầu tiên, dist = [0, ∞, ∞, ∞, ∞, ∞] và mark = [0, 0, 0, 0, 0, 0] (ta coi 0 là false và 1 là true).
• Ta chọn u = 1 do dist[1] = 0 nhỏ nhất và thoả mãn mark[1] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 1.
  • Xét v = 2, ta thấy dist[1] + độ dài cạnh (1, 2) = 3 < dist[2] = ∞ nên dist[2] = 3

• • Do không còn đỉnh nối từ đỉnh 1 nên ta kết thúc xét đỉnh 1 và đánh dấu mark[1] = 1

• Khi này, dist = [0, 3, ∞, ∞, ∞, ∞] và mark = [1, 0, 0, 0, 0, 0]
• Ta chọn u = 2 do dist[2] = 3 nhỏ nhất và thoả mãn mark[2] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 2.
  • Xét v = 3, ta thấy dist[2] + độ dài cạnh (2, 3) = 8 < dist[3] = ∞ nên dist[3] = 8
  • Do không còn đỉnh nối từ đỉnh 2 nên ta kết thúc xét đỉnh 2 và đánh dấu mark[2] = 1
• Khi này, dist = [0, 3, 8, ∞, ∞, ∞] và mark = [1, 1, 0, 0, 0, 0]
• Ta chọn u = 3 do dist[3] = 8 nhỏ nhất và thoả mãn mark[3] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 3.
  • Xét v = 4, ta thấy dist[3] + độ dài cạnh (3, 4) = 11 < dist[4] = ∞ nên dist[4] = 8
  • Do không còn đỉnh nối từ đỉnh 3 nên ta kết thúc xét đỉnh 3 và đánh dấu mark[3] = 1
• Khi này, dist = [0, 3, 8, 11, ∞, ∞] và mark = [1, 1, 1, 0, 0, 0]
• Ta chọn u = 4 do dist[4] = 11 nhỏ nhất và thoả mãn mark[4] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 4.
  • Xét v = 5, ta thấy dist[4] + độ dài cạnh (4, 5) = 3 < dist[5] = ∞ nên dist[5] = 3
  • Do không còn đỉnh nối từ đỉnh 4 nên ta kết thúc xét đỉnh 4 và đánh dấu mark[4] = 1
• Khi này, dist = [0, 3, 8, 11, 3, ∞] và mark = [1, 1, 1, 1, 0, 0]
• Ta chọn u = 5 do dist[5] = 3 nhỏ nhất và thoả mãn mark[5] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 5.
  • Xét v = 3, ta thấy dist[45] + độ dài cạnh (4, 3) = 7 < dist[3] = 8

Đây chính là lúc mà điều bất thường xuất hiện. Trong lập luận đã nêu ở bài trước, chúng ta biết rằng một đỉnh khi được đánh dấu là đã xét xong thì đường đi từ đỉnh nguồn đến đỉnh đó phải là đường đi ngắn nhất. Tuy nhiên, ta thấy ở trong ví dụ trên, khi một đỉnh được đánh dấu là đã xét thì vẫn tồn tại đường đi khác ngắn hơn. Vậy thì lý do là tại sao?

Ta thấy rằng, đường đi  có tổng trọng số là , là một số âm. Như đã biết, mọi số nguyên khi cộng với số âm thì đều cho ra kết quả nhỏ hơn nó. Do đó, chỉ cần ta đi qua đường đi trên vô hạn lần thì độ dài đường đi sẽ giảm vô hạn lần. Lúc này, không tồn tại đường đi ngắn nhất từ đỉnh 1 đến các đỉnh 3, đỉnh 4 và đỉnh 5. Đường đi  được gọi làm một chu trình âm.

Chu trình âm là một chu trình mà tổng trọng số các cạnh thuộc chu trình đó là số âm. Khi xuất hiện chu trình âm thì sẽ không tồn tại đường đi ngắn nhất giữa một số cặp đỉnh.

Ý tưởng

Vậy thì làm sao để thoát ra khỏi “hố đen” chu trình âm? Thực ra ý tưởng khá đơn giản. Ta thấy với một đơn đồ thị, nếu có  đỉnh thì sẽ tồn tại tối đa  cạnh nối đến một đỉnh. Do đó, nếu không tồn tại chu trình âm, một đỉnh sẽ chỉ được cập nhật tối đa  lần. Do đó ta chỉ cần kiểm tra nếu một đỉnh bị cập nhật  lần có nghĩa là tồn tại chu trình âm và không có đường đi ngắn nhất giữa đỉnh nguồn và đỉnh đó.

Thuật toán Bellman-Ford

Bài toán đặt ra

Cho một đồ thị có hướng gồm  đỉnh (đánh số từ 1 đến ),  cạnh có hướng và có trọng số là số nguyên, có thể âm hoặc dương. Cho một đỉnh , hãy tìm độ dài đường đi ngắn nhất từ đỉnh  đến tất cả các đỉnh còn lại.

Nếu như không tồn tại đường đi giữa hai đỉnh, in ra -1.

Nếu như không tồn tại đường đi ngắn nhất giữa hai đỉnh, in ra -2.

Input:

• Dòng : Gồm 3 số nguyên  lần lượt thể hiện cho số đỉnh của đồ thị, số cạnh của đồ thị và đỉnh yêu cầu
• Dòng : Mỗi dòng gồm 3 số nguyên  thể hiện một cạnh có hướng nối từ đỉnh  đến đỉnh  và có trọng số w

Output:

• Gồm  dòng, dòng thứ  thể hiện độ dài đường đi ngắn nhất từ đỉnh  đến đỉnh 

Ví dụ:

Giải thích ví dụ:

Đây chính là đồ thị ở ví dụ phía trên.

Ý tưởng

Ý tưởng của thuật toán Bellman-Ford như sau:

Ta sẽ xét lần lượt tất cả cách cạnh của đồ thị. Với mỗi cạnh nối từ đỉnh  đến đỉnh , ta sẽ xem thử cập nhật đường đi ngắn nhất từ đỉnh nguồn đến đỉnh  thông qua đường đi từ  đến . Do ta đã nhận xét ở trên một đỉnh chỉ cập nhật tối đa  lần nên tại lần cập nhật thứ , nếu như vẫn có đỉnh được cập nhật nghĩa là đỉnh đó thuộc chu trình âm.

Cách cài đặt

Về cơ bản thì thuật toán Bellman-Ford khá dễ cài đặt, chỉ có một điểm khác đó là ta sẽ dùng một cấu trúc để lưu trữ các cạnh với 3 thông tin gồm hai đỉnh và trọng số của cạnh đó. Chi tiết các bạn hãy quan sát phần code phía bên dưới.

Code

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

typedef long long ll;

const int MaxN = 1 + 1e2;
const ll INF = 1e18;

int n, m, s, mark[MaxN];
ll dist[MaxN];

class Edge{
    public:
        int u, v, weight;

        Edge(int _u, int _v, int _weight): u(_u), v(_v), weight(_weight){}
};

vector<Edge> edges;

void Bellman_Ford(){
    fill(dist + 1, dist + n + 1, INF);
    dist[s] = 0;

    for(int i = 1; i <= n; i++){
        for(Edge e : edges){
            if(dist[e.u] + e.weight < dist[e.v]){
                // Tại lần cập nhật thứ n, nếu đỉnh vẫn được cập nhật nghĩa là nó thuộc chu trình âm và ta đánh dấu nó 
                if(i == n) mark[e.v] = 1;
                dist[e.v] = dist[e.u] + e.weight;
            }
        }
    }
}

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i++){
        int u, v, weight;
        cin >> u >> v >> weight;
        edges.push_back(Edge(u, v, weight));
    }
    Bellman_Ford();
    for(int i = 1; i <= n; i++)
    if(!mark[i]){ 
        if(dist[i] == INF) cout << "-1" << endl;
        else cout << dist[i] << endl;
    } else cout << "-2" << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

Độ phức tạp

Nhìn vào đoạn code trên, ta thấy có một vòng lặp duyệt qua tất cả các cạnh được lặp lại  lần. Do đó, độ phức tạp thuật toán là .

So sánh các thuật toán

	Thuật toán Floyd	Thuật toán Dijikstra	Thuật toán Bellman-Ford
Mục đích	Tìm đường đi ngắn nhất giữa mọi cặp đỉnh	Tìm đường đi ngắn nhất từ đỉnh nguồn đến các đỉnh còn lại	Tìm đường đi ngắn nhất từ đỉnh nguồn đến các đỉnh còn lại
Thời gian code	Nhanh	Lâu	Nhanh
Tìm được chu trình âm	Không	Không	Có
Độ phức tập thời gian

Kết luận

Qua bài này chúng ta đã nắm về Tìm kiếm đường đi ngắn nhất trên đồ thị với thuật toán Bellman-Ford

Bài sau chúng ta sẽ tìm hiểu về Loang

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Tải xuống

Tài liệu

Nhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Tìm kiếm đường đi ngắn nhất trên đồ thị (Bellman-Ford) dưới dạng file PDF trong link bên dưới.

Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com

Đừng quên like và share để ủng hộ Kteam và tác giả nhé!

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

CỘNG ĐỒNG HỎI ĐÁP HOWKTEAM.COM

GROUP THẢO LUẬN FACEBOOK