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

Cấu trúc dữ liệu và giải thuật

0.0 (0 đánh giá)
Tạo bởi Katsu Cập nhật lần cuối 17:49 07-07-2022 1.553 lượt xem 0 bình luận
Tác giả/Dịch giả: huulam3011 K9
Học nhanh

Danh sách bài học

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ề:

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, ∞, ∞, ∞, ∞, ∞]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, ∞, ∞, ∞, ∞]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, ∞, ∞, ∞]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, ∞, ∞]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, ∞]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ì do là tại sao?

Ta thấy rằng, đường đi 3\rightarrow 4\rightarrow 5\rightarrow 3 có tổng trọng số là 3+(-8)+4=-1, 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 3\rightarrow 4\rightarrow 5\rightarrow 3 đượ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ó n đỉnh thì sẽ tồn tại tối đa n-1 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 n-1 lần. Do đó ta chỉ cần kiểm tra nếu một đỉnh bị cập nhật n 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 n đỉnh (đánh số từ 1 đến n), m 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 s, hãy tìm độ dài đường đi ngắn nhất từ đỉnh s đế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 1: Gồm 3 số nguyên n, m, s 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 (1\leq n,m\leq 10^{4}, 1 \leq s \leq n)
  • Dòng 2_{\dots}m+1: Mỗi dòng gồm 3 số nguyên u,v,w thể hiện một cạnh có hướng nối từ đỉnh u đến đỉnh v và có trọng số w w(1\leq u,v \leq n, |w| \leq 10^{9})

Output:

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

Ví dụ:

Input Output

6 6 1

1 2 3

2 3 5

3 4 3

4 5 -8

5 3 4

6 5 2

0

3

-2

-2

-2

-1

Giải thích ví dụ:

Bellman_Ford

Đâ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 u đến đỉnh v, ta sẽ xem thử cập nhật đường đi ngắn nhất từ đỉnh nguồn đến đỉnh v thông qua đường đi từ u đến v. Do ta đã nhận xét ở trên một đỉnh chỉ cập nhật tối đa n-1 lần nên tại lần cập nhật thứ n, 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;
}

Độ 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 n lần. Do đó, độ phức tạp thuật toán là O(m \times n).


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
Độ phức tập thời gian O(n)^{3} O(m \times logn) O(m \times n)

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ó”.


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ê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.

Nội dung bài viết

Tác giả/Dịch giả

Mình là Nguyễn Hữu Lâm, một người có niềm đam mê rất lớn đối với lập trình. Hiện tại, mình đang là sinh viên Khoa học máy tính của Đại học Bách Khoa Hà Nội. Mong muốn của mình là có thể chia sẻ những kiến thức mà bản thân có cho mọi người, học hỏi, kết bạn với tất cả những người có cùng đam mê với mình.


K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Cấu trúc dữ liệu và giải thuật

Bạn đã từng đau đầu với các cấu trúc stack, queue,.. hoặc cảm thấy cực kỳ khó khăn với các thuật toán sắp xếp, tìm kiếm được sử dụng trong lập trình. Đừng lo lắng! Trong khoá học này, chúng ta sẽ cùng nhau tìm hiểu một cách đơn giản nhất về cấu trúc dữ liệu và giải thuật, cũng như giúp bạn nắm rõ hơn về các kiến thức này.

Hãy cùng xem cấu trúc dữ liệu và giải thuật có gì đáng sợ không nhé!

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.