定向未加權圖中最長的非循環路徑

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作爲權重。