เส้นทางยาวที่สุดในกราฟมีทิศทางไม่มีวงจร (Longest Path in DAG)

กำหนดกราฟมีทิศทางไม่มีวงจร (DAG) ที่มีน้ำหนักบนเส้นเชื่อม และโหนดต้นทาง ต้องการหาระยะทางยาวที่สุดจากโหนดต้นทางไปยังโหนดอื่นๆ ทั้งหมดในกราฟ

วิธีแก้คือการเรียงลำดับโหนดแบบ Topological Sorting เก็บผลลัพธ์ไว้ใน Stack จากนั้นนำโหนดออกจาก Stack ทีละตัวเพื่อคำนวณระยะทางยาวที่สุดสำหรับแต่ละโหนด

การรับค่าและแสดงผล

Input: เมทริกซ์ต้นทุนของกราฟ (เหมือนตัวอย่าง Shortest Path)
Output: Longest Distance from Source Vertex 1
Infinity 0 2 9 8 10

อัลกอริทึม

topoSort(u, visited, stack) - เรียงลำดับโหนดแบบ Topological (เหมือน Shortest Path)

longestPath(start) - หาระยะทางยาวที่สุด

Begin
  ทำเครื่องหมายทุกโหนดว่าไม่ได้เยี่ยมชม
  for ทุกโหนด i ในกราฟ do
    if i ไม่ได้เยี่ยมชม then topoSort(i, visited, stack)
  done
  
  ตั้งค่าระยะทางทุกโหนด = -INF
  dist[start] := 0
  
  while stack ไม่ว่าง do
    pop stack ให้เป็น nextVert
    if dist[nextVert] != -INF then
      for ทุกโหนด v ที่ติดกับ nextVert do
        if cost[nextVert, v] != -INF then
          if dist[v] < dist[nextVert] + cost[nextVert, v] then
            dist[v] := dist[nextVert] + cost[nextVert, v]
          end if
        end if
      done
    end if
  done
  
  for ทุกโหนด i do
    if dist[i] = -INF แสดง "Infinity" ไม่เช่นนั้นแสดง dist[i]
  done
End

ตัวอย่างโค้ด (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;
  for(int v = 0; v < NODE; v++) {
    if(cost[u][v]) {
      if(!visited[v]) topoSort(v, visited, stk);
    }
  }
  stk.push(u);
}

void longestPath(int start) {
  stack<int> stk;
  int dist[NODE];
  bool vis[NODE];
  
  for(int i = 0; i < NODE; i++) vis[i] = false;
  for(int i = 0; i < NODE; i++)
    if(!vis[i]) topoSort(i, vis, stk);
  
  for(int i = 0; i < NODE; i++) dist[i] = INF;
  dist[start] = 0;
  
  while(!stk.empty()) {
    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);
}

ผลลัพธ์

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