如何找到無向加權圖中最長（最重）的軌跡？

Question

我有美國空間地圖連接城市與權重（距離）。我想在這張地圖上找到最長的（權重最大的）路線。

• 每個邊緣被訪問0或1倍
• 每個節點可以訪問[0，INF）次。

沒有要求所有節點或邊緣需要訪問。

方法和prolog資源建議會很好。

Answer 1

我不知道我是否正確的，但你可以嘗試以下方法：

1. 您可以檢查圖是歐拉。如果是這樣，你的問題是找到歐拉電路，這可以在多項式時間完成。

2. 否則你有一個問題，因爲如果我沒有錯，你必須找到最大（可能是誘導）歐拉子圖，這是NP難。

當然，一切都假設所有的權重都是非負的。