เส้นทางที่สั้นที่สุดในกราฟ Acyclic แบบกำกับทิศทาง

ให้กราฟ acyclic กำกับแบบถ่วงน้ำหนักหนึ่งกราฟ มีจุดยอดแหล่งที่มาอื่นด้วย ตอนนี้เราต้องหาระยะทางที่สั้นที่สุดจากโหนดเริ่มต้นไปยังจุดยอดอื่นทั้งหมดในกราฟ

ในการตรวจจับระยะทางที่น้อยกว่า เราสามารถใช้อัลกอริธึมอื่น เช่น Bellman-Ford สำหรับกราฟที่มีน้ำหนักติดลบ สำหรับน้ำหนักที่เป็นบวก อัลกอริธึมของ Dijkstra ก็มีประโยชน์เช่นกัน สำหรับ Directed Acyclic Graph เราจะใช้เทคนิคการจัดเรียงทอพอโลยีเพื่อลดความซับซ้อน

อินพุตและเอาต์พุต

Input:
The cost matrix of the graph.
0   5  3 -∞ -∞ -∞
-∞  0  2  6 -∞ -∞
-∞ -∞  0  7  4  2
-∞ -∞ -∞  0 -1  1
-∞ -∞ -∞ -∞  0 -2
-∞ -∞ -∞ -∞ -∞  0

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

อัลกอริทึม

topoSort(u, เยี่ยมชม, stack)

ป้อนข้อมูล :เริ่มต้นโหนด u, รายการที่เข้าชมเพื่อติดตาม, สแต็ก
ผลลัพธ์: จัดเรียงโหนดด้วยวิธีทอพอโลยี

Begin
   mark u as visited
   for all vertex v, which is connected with u, do
      if v is not visited, then
         topoSort(v, visited, stack)
   done
   push u into the stack
End

เส้นทางที่สั้นที่สุด(เริ่มต้น)

ป้อนข้อมูล - โหนดเริ่มต้น
ผลลัพธ์ − รายการระยะทางที่สั้นที่สุดของจุดยอดทั้งหมดจากโหนดเริ่มต้น

Begin
   initially make all nodes as unvisited
   for each node i, in the graph, do
      if i is not visited, then
         topoSort(i, visited, stack)
   done

   make distance of all vertices as ∞
   dist[start] := 0
   while stack is not empty, do
      pop stack item and take into nextVert
      if dist[nextVert] ≠∞, then
         for each vertices v, which is adjacent with nextVert, do
            if cost[nextVert, v] ≠∞, then
               if dist[v] > dist[nectVert] + cost[nextVert, v], then
                  dist[v] := dist[nectVert] + cost[nextVert, v]
         done
   done

   for all vertices i in the graph, do
      if dist[i] = ∞, then
         display Infinity
      else
         display dist[i]
   done
End

ตัวอย่าง

#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;       //set as the node v is visited
   for(int v = 0; v<NODE; v++) {
      if(cost[u][v]) {       //for allvertices v adjacent to u
         if(!visited[v])
            topoSort(v, visited, stk);
      }
   }

   stk.push(u);       //push starting vertex into the stack
}

void shortestPath(int start) {
   stack<int> stk;
   int dist[NODE];

   bool vis[NODE];
   for(int i = 0; i<NODE;i++)
      vis[i] = false;          // make all nodes as unvisited at first

   for(int i = 0; i<NODE; i++)     //perform topological sort for vertices
      if(!vis[i])
         topoSort(i, vis, stk);

   for(int i = 0; i<NODE; i++)
      dist[i] = INF;       //initially all distances are infinity
   dist[start] = 0;       //distance for start vertex is 0

   while(!stk.empty()) {    //when stack contains element, process in topological order
      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]<<" ";
}

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