给出了一个加权有向无环图。还提供了另一个源顶点。现在,我们必须在图中找到从起始节点到所有其他顶点的最长距离。
我们需要使用拓扑排序技术对节点进行排序,并将拓扑排序后的结果存储到堆栈中。之后,反复从堆栈中弹出并尝试查找每个顶点的最长距离。
Input: The cost matrix of the graph. 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ -∞ 0 -1 1 -∞ -∞ -∞ -∞ 0 -2 -∞ -∞ -∞ -∞ -∞ 0 Output: Longest Distance from Source Vertex 1 Infinity 0 2 9 8 10
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
longestPath(开始)
输入- 起始节点。
输出-距起始节点的所有顶点的最长距离的列表。
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 longestPath(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 << "Longest Distance From Source Vertex "<<start<<endl; longestPath(start); }
输出结果
Longest Distance From Source Vertex 1 Infinity 0 2 9 8 10