给出了一个加权有向无环图。还提供了另一个源顶点。现在,我们必须在图中找到从起始节点到所有其他顶点的最短距离。
为了检测较小的距离,我们可以对负负图使用另一种算法,例如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