訪問所有節點的最短路徑

Question

我正在尋找一種對我來說似乎很典型的算法，但似乎常見的解決方案都只是有點不同。

在無向圖中，我想要訪問每個節點的最短路徑。節點可以重新訪問，我不必返回到開始節點。

The 旅行商問題似乎增加了限制，即每個節點只能訪問一次，並且路徑必須返回到它開始的位置。

最小生成樹可能是解決方案的一部分，但此類算法僅提供樹，而不是最小路徑。另外，因爲它們是樹木，因此沒有循環，所以它們強制回溯循環可能更有效。

Answer 1

您可以通過轉換圖形將其降至正常的旅行推銷員問題。

首先，計算每對節點的最小距離。你可以使用Floyd-Warshall算法。一旦你擁有了它，就構建了完整的圖，其中的節點ü和v之間的邊緣爲ü到v成本最低。

然後，你可以申請一個正常的TSP算法，你不必再重溫節點，這已經隱藏在邊緣的成本。