有向无环图中的最短路径

给出了一个加权有向无环图。还提供了另一个源顶点。现在,我们必须在图中找到从起始节点到所有其他顶点的最短距离。

为了检测较小的距离,我们可以对负负图使用另一种算法,例如Bellman-Ford,对于正负数,Dijkstra算法也很有帮助。在这里,对于有向无环图,我们将使用拓扑排序技术来降低复杂度。

输入输出

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,已访问,堆栈)

输入:起始节点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

shortestPath(开始)

输入-起始节点。
输出-距起始节点的所有顶点的最短距离的列表。

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

以上是 有向无环图中的最短路径 的全部内容, 来源链接: utcz.com/z/337987.html

回到顶部