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

Question

可以使用什么算法来查找未加权有向无环图中的最长路径？

Answer 1

动态编程.它也在最长路径问题中被引用,因为它是DAG.

来自维基百科的以下代码:

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

只要图形是非循环的,您需要做的就是否定边权重并运行任何最短路径算法.

编辑:显然,您需要一个支持负权重的最短路径算法.此外,维基百科的算法似乎有更好的时间复杂性,但我会在此留下我的答案以供参考.