查找有向图中节点数最多的路径

在有向图中查找节点数最多的路径是一种好方法吗？查找有向图中节点数最多的路径

我想我可以遍历每个节点的深度图，找出哪个路径有最多的节点，但我想知道是否有更好的方法。

提及：图形保证没有周期。

来源

2012-03-29 Mihai Bişog

你的意思是你想要一个算法来解决[最长路径问题]（http://en.wikipedia.org/wiki/Longest_path_problem）？ – 2012-03-29 14:45:57

你的图是一棵树。好吧差不多...... :) – 2012-03-30 10:54:20

您有一个有向无环图（DAG），并且您想查找具有最大节点数的路径。这实际上在DAG中找到了longest path。

这个问题在多项式时间内可以解决DAG。阅读更多关于它在这里： - Wikipedia.

来源

2012-03-29 14:47:43

感谢您的提示。我最终通过使用Floyd-Warshall算法来解决这个问题，每个边的权重都是-1。 – 2012-04-01 12:30:00

如果图有一个循环，那么是“无限”长度的路径。

如果图是非循环的：您应该运行拓扑排序。然后：

foreach(node in topological_sort_order) { 
    foreach(prev_node in neibhours[node]) { 
     // there is edge from prev_node to node 
     // since vertices are sorted in topological order than 
     // value for longest_path[prev_node] is already computed 
     longest_path[node] = max(longest_path[node], longest_path[prev_node] + 1); 
    } 
}

来源

2012-03-29 14:48:35

由于您的输入是有向图，而不是向无环图则是NP完全和提到的解决方案不起作用。但是，正如logic_max所说：这是最长的路径问题，并且通过给每条边设置一个成本来减少这个问题。

来源

2012-03-30 03:43:07 AJed

查找有向图中节点数最多的路径

回答

相关问题