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

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

สำหรับกราฟที่มีน้ำหนักลบ สามารถใช้ Bellman-Ford สำหรับน้ำหนักบวก ใช้ Dijkstra แต่สำหรับ DAG เราสามารถใช้เทคนิค Topological Sorting เพื่อลดความซับซ้อนได้

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

Input: เมทริกซ์ต้นทุนของกราฟ
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

Output: Shortest Distance from Source Vertex 1
Infinity 0 2 6 5 3

อัลกอริทึม

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

shortestPath(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 shortestPath(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 << "Shortest Distance From Source Vertex " << start << endl;
  shortestPath(start);
}

ผลลัพธ์

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