顛倒Floyd-Warshall

Question

我有一個快速的問題。我知道這是NP的問題。如果您收到每對節點之間正確的反轉算法Floyd-Warshall最長路徑？

Answer 1

這是行不通的。問題是最長路徑問題的結構是根本不同的。也許這不是很明顯，但Floyd-Warshall使用最短路徑問題的最優子結構屬性。也就是說，從A到B到C的最短路徑由A到C的最短路徑和從C到B的最短路徑構成。

最長的路徑問題沒有那個屬性，你可以看到這個很明顯在一個3節點例如：

A 
/\ 
    B---C 

最長路徑（回想LPP要求一個簡單路徑，所以它仍然在週期的存在良好定義的）從A到B是明顯A， C，B（或者更一般地說，任何地方最長的路徑都有長度2），但是從A到C和B到C兩者的最長路徑包括A，所以這些塊甚至不能組合以形成val ID路徑。這通常是一個問題 - 如果您嘗試從兩個子路徑中構建完整的最長路徑，則子路徑必須「彼此瞭解」，以便它們不會重複節點。

當然，你也可以非常容易地證明LPP是NP-hard（從哈密爾頓路徑問題中減少），它不能證明它不能在多項式時間內求解，但如果它看起來你已經這樣做了你應該對結果很懷疑。畢竟，我們不太可能在一個閒暇的下午隨便解決P？= NP問題，尤其是沒有明顯的方式。