Dijkstra在DAG中的最長路徑

Question

我想知道是否有可能使用Dijkstra算法在有向非循環路徑中查找最長路徑。我知道，由於負成本週期，在一般圖中找不到Dijkstra最長的路徑。但我認爲它應該在DAG中運作。通過Google，我發現了很多相沖突的來源。有人說它有效，有人說它不起作用，但我沒有找到證據或反例。有人能指點我一個證明或反例嗎？

Answer 1

我想到了這個問題，我認爲這是不可能的。我認爲，非循環是不夠的。

例如：

我們想在這個dag中從a到c。

a - > b - > c 
|   /\ 
v   | 
d - - - - - 

DC的長度爲4

廣告長度爲1

所有其他人都長2

如果你只是用max函數替換min函數，算法將導致ABC但最長的路徑是adc。

我發現了兩個特殊的情況下，您可以使用Dijkstra算法計算最長路徑：

1. 該圖不僅向無環，也是非週期性如果刪除了方向。換句話說：它是一棵樹。因爲在一棵樹中最長的路徑也是最短的路徑。
2. 該圖只有負權重。然後，您可以使用max而不是min來查找最長的路徑。但是這隻有在權重真的是負數時才起作用。如果你只是反轉正面權重，它將無法正常工作。

Answer 2

唯一的要求是不要有負循環。如果你沒有這些週期，那麼你可以通過從負權重中加入所有權重的最高絕對值來重新映射負值。這樣你就會失去負面的力量，因爲所有的重量都將等於或大於零。因此，總結一點，唯一擔心的是沒有一個負面循環。

Answer 3

是有三種可能的方式應用Dijkstra算法，它們都將無法工作：
1.Directly使用「最大」操作，而不是「分」的操作。
2.將所有正面權重轉換爲負值。然後找到最短的路徑。
3.給出一個非常大的正數M.如果一個邊的權重是w，現在用M-w代替w。然後找到最短的路徑。

對於DAG，關鍵路徑法將工作：
1：找到一個拓撲排序。
2：找到關鍵路徑。
見[霍洛維茨1995] E. Howowitz，S.薩尼和D.梅塔，在C數據結構++基礎，計算機科學出版社，紐約，1995年

Answer 4

我建議你修改Dijkstra算法取倒邊緣重量的值。由於該圖是非循環的，因此該算法不會進入無限循環，使用負權重來保持優化。更重要的是，現在積極的權重變成負數，但是，再次，沒有周期。如果您不允許重新插入訪問節點（即停止兩個節點之間的無止境跳轉，因爲添加負值始終會更好），即使圖形爲但無向也是如此。

Answer 5

最長距離問題沒有最優子爲任何圖形，DAG或沒有。然而，圖G上的任何最長距離問題等價於變換圖G'= - G中的最短距離問題，即每個邊權重的符號相反。

如果變換圖G'預計具有負邊和週期，那麼Bellman-Ford算法用於尋找最短距離。然而，如果G保證只有非負權重（即G'是非正權重），那麼Dijkstra的算法可能是比Bellman-Ford更好的選擇。 （見'Evgeny Kluev'對於graph - Dijkstra for The Single-Source Longest Path的迴應）如果G是一個DAG，那麼G'也將是一個DAG。對於DAG，我們有更好的算法來尋找最短距離，應該選擇Dijkstra或Bellman-Ford的算法。

總結：
最長路徑問題沒有最優子，因此在Dijkstra算法修改分鐘權重函數到最大權重函數不會單獨一個圖的工作，無論是DAG或沒有。相反，修改任何最短路徑算法（以及在一個平凡的方式），我們寧可改造G，看看哪些最短路徑算法效果最好的轉化G.

注意

 A-------B 
    |  |    assume: edges A-B, B-C, C-A of same weight 
    |  | 
    +-------C 

我們看到MAX_DIS（A，B）= A-> C->乙
對於 「MAX_DIS」 是最佳的結構中，在上述情況下，關係

MAX_DIS(A,B) = MAX_DIS(A,C) + MAX_DIS(C,B) should be satisfied. 

但是，它不是我們所看到的，MAX_DIS（A，C​​）= A-> B-> C和MAX_DIS（C，B）= C-> A-> B，因此它提供了一個例子，最長距離問題可能不會有最佳的子結構。