定向未加权图中最长的非循环路径

Question

可以使用什么算法找到未加权的定向非循环图中最长的路径？

Answer 1

Dynamic programming。考虑到它是DAG，它也在Longest path problem中引用。

下面的代码从维基百科：

algorithm dag-longest-path is 
    input: 
     Directed acyclic graph G 
    output: 
     Length of the longest path 

    length_to = array with |V(G)| elements of type int with default value 0 

    for each vertex v in topOrder(G) do 
     for each edge (v, w) in E(G) do 
      if length_to[w] <= length_to[v] + weight(G,(v,w)) then 
       length_to[w] = length_to[v] + weight(G, (v,w)) 

    return max(length_to[v] for v in V(G)) 

Answer 2

只要该图是无环，所有你需要做的是否定的边缘权重和运行任何最短路径算法。

编辑：很明显，你需要一个支持负权重的最短路径算法。另外，来自维基百科的算法似乎有更好的时间复杂性，但我会在这里留下我的答案供参考。

Answer 3

维基百科有一个算法：http://en.wikipedia.org/wiki/Longest_path_problem

看起来他们使用的权重，但应与权重的工作都设置为1。

Answer 4

可以通过关键路径方法来解决：
1.找到一个拓扑排序
2.找到关键路径
参见[Horowitz 1995]，Fundamentals of Data Structures in C++，Computer Science Press，New York。

贪婪策略（例如Dijkstra）不会工作，不管：1。使用“max”而不是“min”2.将正面权重转换为负面3.给出非常大的数字M并使用M-w作为权重。