今天我在上讀到的longest path problem的介紹，它在加權的有向圖中詢問通過兩個頂點的最長的簡單路徑。作者使用了一個很好的例子來說明動態規劃對於最長路徑問題的失敗，因爲它不存在一個總是帶有最優子結構的好的最優結構。有人評論說這個問題實際上是NP完全的。所以它一定很難。爲什麼我們不能把最長路徑變成最短路徑？
現在，這裏是我的問題：除了指定的每一個邊緣的積極權重k> 0，如果我們只是將負權重與體重-K各自的優勢？那麼每個「最長路徑」將自動成爲最短路徑，並且如果根據定義在最短路徑中沒有環路，則在相應的最長路徑中不應該存在任何環路。因此，使用相當常見的技巧，我們可以將最長路徑問題轉化爲最短路徑問題。
有人能指出我在推理中的錯誤嗎？我認爲一定是錯的，但不知道它是什麼。由於顯而易見的原因，我的觀點是不正確的。閱讀本書中提供的僞代碼，似乎最短路徑的算法並不禁止使用負權重，並且畢竟所有的東西都可以通過增加一個足夠大的常數使其成爲正值來「提升」。我是算法的初學者，所以這個問題對專家來說可能是微不足道的。
在你的推理錯誤是這一行：
如果在定義的最短路徑無環路，應該不會出現在相應的最長路徑任何循環。
如果你有一個圖，其中所有邊緣有負重量（可以在您所描述的轉變發生），並有一個負循環，再有就是對週期的任何兩個節點之間沒有最短路徑，因爲它們之間的任何路徑可以通過越來越多地遵循該循環而降低其成本。由於在這種情況下沒有最短路徑，所以你的推理失效了。
現在，您可以爭辯說，您應該尋找最短的簡單的節點之間的路徑（即沒有重複邊的路徑）。不幸的是，這個問題也是NP難題，所以這個減少並不會給你帶來任何收益。
希望這會有所幫助！
嗨！這裏是我的問題：我的意思是最短的簡單路徑問題，我不明白你爲什麼說它是NP難。我在書中讀到，這可以通過動態編程來解決，因爲它具有最佳結構。你的意思是別的還是我感到困惑？ – 2015-02-23 04:24:26
@Bombyxmori最短的簡單路徑只能在沒有負循環的圖表中以多項式時間找到。如果存在負循環，DP算法會失敗。 – templatetypedef 2015-02-23 06:24:33
我明白了。我需要考慮一下。由於本書中的DP算法似乎完全適用於負重案例，因此我認爲這將貫穿始終。感謝您指出。 – 2015-02-23 06:33:49
如果在定義的最短路徑無環路，應該 沒有在相應的最長路徑
任何循環...等特定原來的問題是在多項式時間內可解。如果特定的原始問題是DAG，那麼這種方法在線性時間內解決它。
的複雜性聲明並沒有說所有的圖是難以解決的，只是有的。
從你自己的鏈接：
與此相反的最短路徑問題，可以在 多項式時間內以圖表來解決無負重週期，最長 路徑問題是NP難的，意義除非P = NP，否則它不能在任意圖的 多項式時間中求解。
[...]
對於大多數圖形，因爲它會在-G負長度的 週期這種轉化是沒有用的。但是如果G是有向無環圖，那麼不能創建負循環，並且通過在-G中應用線性時間算法尋找最短的路徑，並且G中的最長路徑可以是線性時間中找到的 ，其也是有向非循環圖形。
對不起！修復了死鏈接。 – 2015-02-23 04:01:37