Ta bắt đầu khởi tạo các mảng n phần tử: label, length, prev. Gán label[k] = 1, length[k] = -1 (inf), prev[k] = -1 với k chạy từ 0 -> n – 1. Gán length[first] = 0.

Chọn đỉnh v trong mảng sao cho length[k] là nhỏ nhất. Sau đó gán label[k] = 0 (Đã đánh dấu).

Tạo vòng lặp với biến chạy k, xét nếu label[k] = 1 (Chưa đánh dấu) và có đường đi từ v -> k: Nếu length[k] > length[v] + trọng số từ v -> k hoặc length[k] = inf, có nghĩa là nếu ta tìm được 1 đường từ v -> k là nhỏ nhất, hoặc là chưa tìm được đường nào ngắn nhất (inf) => Gán length[k] = length[v] + trọng số v -> k, prev[k] = v (Tạo vết chân đỉnh trước đó).

Nếu label[last] = 0 (Đã đánh dấu đỉnh đến), kết thúc vòng lặp. Nếu không thì quay lại bước 2.

VD: Ta có 1 đồ thị như sau

Ta cần chỉ ra đường đi ngắn nhất từ đỉnh 1 tới 6. Vậy các bước sẽ như thế nào?

2. Viết và chạy thuật toán

Để đơn giản, trong phần này tôi dùng ma trận kề, và mỗi các đỉnh được đặt tên theo số thứ tự 0,1,2.

/**
Trong nay, cac dinh khong co canh noi voi nhau se co khoang cach la -1
/
public int[] dijkstra(int[][] graph, int s){
  int [] dist = new int[graph.length];
  for(int i = 0; i < graph.length; i++){
    dist[i] = Integer.MAX_VALUE;
  }
  dist[s] = 0;
  int [] visit = new int[graph.length]; 
  for(int i = 0; i < graph.length; i ){
    int v = closestVertice(graph[s], visit);
    for(int j = 0; j < graph[v].length; j){
      if (graph[v][j] != -1){ // neu co canh noi giua v va j
        int currentDist = dist[v] + graph[v][j];
        if (currentDist < dist[j]){
          dist[j] = currentDist;
        }
      }
    }
  }
  return dist;
}
/*
Chon ra dinh o gan s nhat va danh dau dinh do la da tham
*/
public int closestVertice(int[] adjacentVertices, int[] visit){
  int closest = -1;
  int minDist = Integer.MAX_VALUE;
  for(int i = 0; i < adjacentVertices.length; i ++){
    if (visit[i] == 0 && adjacentVertices[i] < minDist){
      closest = i;
      minDist = adjacentVertices[i];
    }
  }
  visit[closest] = 1;
  return closest;
}

Output của thuật toán trên sẽ là:

Distance from '0' to '0':0
Distance from '0' to '1':2
Distance from '0' to '2':3
Distance from '0' to '3':4
Distance from '0' to '4':4

3.Đánh giá độ phức tạp

Độ phức tạp của thuật toán trên sẽ là O(V2).

Nếu ta sử dụng một hàng đợi ưu tiên (priority queue), ví dụ như Binary heap, và sử dụng danh sách kề thì độ phức tạp của thuật toán sẽ bị giảm xuống còn O((V+E)∗logV).

Nguyên nhân là, với danh sách kề, thời gian để duyệt các cạnh và các đỉnh sẽ là O(E+V) thay vì O(V2) như ma trận kề. Ngoài ra, với binary heap, việc tìm đỉnh gần nhất ở

closestVertice(graph[s], visit);

sẽ chỉ còn O(1) thay vì O(V). Vì thế ta cần nhập khoảng cách tới các đỉnh xung quanh vào binary heap bằng cách bỏ các đỉnh đó ra khỏi heap rồi thêm lại, cái này mất O(logV).

Vậy cuối cùng độ phức tạp sẽ là O((V+E)∗logV).

Trên đây là bài viết về "Tìm đường ngắn nhất bằng thuật toán Dijkstra". Tuỳ theo từng yêu cầu cụ thể mà bạn có thể lựa chọn cách làm hợp lý.

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

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

const int inf = 1e18; const int mx = 1e6 + 5; vector> 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 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

const int inf = 1e18; const int mx = 1e6 + 5; vector> 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: