routes - Dijkstra 或 TSP

Question

我正在开发一个网络应用程序来显示一些点之间的地图和路线。我想知道这些点之间的短途路线。

现在我正在使用dijkstra 算法，但我被要求使用TSP代替。

我希望第一个点和最后一个点相同，使用 dijkstra 我必须将最后一个点设置为相同，但使用 TSP 会自动设置。

两者是相同的算法吗？只是通过这种修改还是不同的算法？

任何可以检查 TSP 伪代码的网页？

Answer 1

旅行推销员问题，顾名思义，讨论最短路线及其从单个节点开始并通过访问其间的所有其他节点返回到该节点的成本

但 Dijkstra 更简单。它只是谈论2个节点之间的最短路线和成本。因此，在您的情况下，如果需要包含介于两者之间的所有节点，那么对 TSP 的建议是有效的。

PS 如果您想在所有节点对之间获得最短的路线和成本，那么您应该选择 Floyd 算法，它基本上是 Dijkstra 的扩展。