数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究有向无环图中的最长路径
现给出一个带权重的有向无环图。另外还提供了一个源点。现在我们必须找出图中起始节点到所有其他节点的最长距离。
我们需要用拓扑排序技术对节点进行排序，拓扑排序后的结果存储到一个栈中。然后反复从栈中 pop 出元素，并尝试找出每个节点的最长距离。
输入和输出
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, visited, stack)
输入：起始节点 u，用于跟踪的 visited 列表，栈。
输出 −按拓扑方式对节点进行排序。
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(start)
输入 − 起始节点。
输出 −从起始节点到所有节点的最长距离列表。
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
更新时间： 2020-06-16
1K+ 查看
广告