遍歷多個位置的算法找到最短路線

Question

我正在爲遊客創建一個程序。他們將離開酒店，讓我們說3個不同的地方（B，C，D）。我需要找到最短的路線來遍歷位置B，C和D.終點並不重要，它可以是任何一個。

可以Dijkstra's Algorithm這樣做嗎？

我需要實現使用PHP的算法。

Answer 1

Dijkstra的算法可以解決這個問題。我不確定它是否最佳。但至少，它解決了你的問題。在最壞的情況下，您可以列舉您到達每個節點的所有訂單（即，BCD,BDC,CDB,CBD,DBC,DCB）。然後運行Dijkstra算法得到最短路徑。以BCD爲例，運行Dijkstra's從酒店到B，從B到C，最後從C到D，得到這個訂單的最短路徑。所有訂單中最短的一個是您的問題的最佳解決方案。