遍历多个位置的算法找到最短路线

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，得到这个订单的最短路径。所有订单中最短的一个是您的问题的最佳解决方案。