Đường đi dài 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 dài nhất từ đỉnh bắt đầu đến tất cả các đỉnh khác trong đồ thị.

Ta cần sắp xếp các nút theo kỹ thuật sắp xếp topo, và kết quả sau sắp xếp topo được lưu vào ngăn xếp. Sau đó lặp lại việc lấy từ ngăn xếp và cố gắng tìm khoảng cách dài nhất cho mỗi đỉnh.

Đầ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 dài nhất từ Đỉnh nguồn 1
Infinity 0 2 9 8 10

Thuật toán

topoSort(u, visited, stack)

Đầu vào: Nút 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

longestPath(start)

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

Đầu ra: Danh sách khoảng cách dài 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 longestPath(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 << "Longest Distance From Source Vertex " << start << endl;
  longestPath(start);
}

Đầu ra

Longest Distance From Source Vertex 1 Infinity 0 2 9 8 10