Đường đi ngắn nhất trong đồ thị có hướng không chu trình (DAG)

Cho một đồ thị có hướng không chu trình (DAG) có trọng số. Một đỉnh nguồn cũng được cung cấp. Ta phải tìm khoảng cách ngắn nhất từ đỉnh bắt đầu đến tất cả các đỉnh khác trong đồ thị.

Để phát hiện khoảng cách nhỏ hơn, ta có thể dùng thuật toán Bellman-Ford cho đồ thị có trọng số âm, với trọng số dương thì thuật toán Dijkstra cũng hữu ích. Ở đây cho DAG, ta sẽ sử dụng kỹ thuật sắp xếp topo để giảm độ phức tạp.

Đầu vào và Đầu ra

Đầu vào: Ma trận chi phí của đồ thị.
0   5   3  -∞  -∞  -∞
-∞  0   2   6  -∞  -∞
-∞ -∞   0   7   4   2
-∞ -∞  -∞   0  -1   1
-∞ -∞  -∞  -∞   0  -2
-∞ -∞  -∞  -∞  -∞   0
Đầu ra: Khoảng cách ngắn nhất từ Đỉnh nguồn 1
Infinity 0 2 6 5 3

Thuật toán

topoSort(u, visited, stack)

Đầu vào: Đỉnh bắt đầu u, danh sách visited để theo dõi, ngăn xếp stack.

Đầu ra: Sắp xếp các nút theo thứ tự topo.

Bắt đầu
  đánh dấu u là đã thăm
  với mọi đỉnh v kết nối với u, thực hiện
    nếu v chưa được thăm thì
      topoSort(v, visited, stack)
  kết thúc
  đẩy u vào stack
Kết thúc

shortestPath(start)

Đầu vào: Nút bắt đầu.

Đầu ra: Danh sách khoảng cách ngắn nhất của tất cả đỉnh từ nút bắt đầu.

Bắt đầu
  ban đầu đánh dấu tất cả nút là chưa thăm
  với mỗi nút i trong đồ thị, thực hiện
    nếu i chưa được thăm thì
      topoSort(i, visited, stack)
  kết thúc
  đặt khoảng cách của tất cả đỉnh là ∞
  dist[start] := 0
  trong khi stack không rỗng, thực hiện
    lấy phần tử stack gán vào nextVert
    nếu dist[nextVert] ≠ ∞ thì
      với mỗi đỉnh v kề với nextVert, thực hiện
        nếu cost[nextVert, v] ≠ ∞ thì
          nếu dist[v] > dist[nextVert] + cost[nextVert, v] thì
            dist[v] := dist[nextVert] + cost[nextVert, v]
      kết thúc
  kết thúc
  với mọi đỉnh i trong đồ thị, thực hiện
    nếu dist[i] = ∞ thì
      hiển thị Infinity
    ngược lại
      hiển thị dist[i]
  kết thúc
Kết thúc

Ví dụ (C++)

#include <iostream>
#include <stack>
#define NODE 6
#define INF 9999
using namespace std;

int cost[NODE][NODE] = {
  {0, 5, 3, INF, INF, INF},
  {INF, 0, 2, 6, INF, INF},
  {INF, INF, 0, 7, 4, 2},
  {INF, INF, INF, 0, -1, 1},
  {INF, INF, INF, INF, 0, -2},
  {INF, INF, INF, INF, INF, 0}
};

void topoSort(int u, bool visited[], stack<int> &stk) {
  visited[u] = true; // đặt nút v là đã thăm
  for(int v = 0; v < NODE; v++) {
    if(cost[u][v]) { // cho tất cả đỉnh v kề với u
      if(!visited[v])
        topoSort(v, visited, stk);
    }
  }
  stk.push(u); // đẩy đỉnh bắt đầu vào stack
}

void shortestPath(int start) {
  stack<int> stk;
  int dist[NODE];
  bool vis[NODE];
  
  for(int i = 0; i < NODE; i++)
    vis[i] = false; // làm tất cả nút chưa thăm ban đầu
  
  for(int i = 0; i < NODE; i++) // thực hiện sắp xếp topo cho các đỉnh
    if(!vis[i])
      topoSort(i, vis, stk);
  
  for(int i = 0; i < NODE; i++)
    dist[i] = INF; // ban đầu tất cả khoảng cách là vô cực
  dist[start] = 0; // khoảng cách đỉnh bắt đầu là 0
  
  while(!stk.empty()) {
    // khi stack chứa phần tử, xử lý theo thứ tự topo
    int nextVert = stk.top(); stk.pop();
    if(dist[nextVert] != INF) {
      for(int v = 0; v < NODE; v++) {
        if(cost[nextVert][v] && cost[nextVert][v] != INF) {
          if(dist[v] > dist[nextVert] + cost[nextVert][v])
            dist[v] = dist[nextVert] + cost[nextVert][v];
        }
      }
    }
  }
  
  for(int i = 0; i < NODE; i++)
    (dist[i] == INF) ? cout << "Infinity " : cout << dist[i] << " ";
}

int main() {
  int start = 1;
  cout << "Shortest Distance From Source Vertex " << start << endl;
  shortestPath(start);
}

Đầu ra

Shortest Distance From Source Vertex 1 Infinity 0 2 6 5 3