algorithm - 在多个点上寻找最短路径

Question

要求:

1. 您需要在图表上访问多个目标(无论顺序如何或访问每个点多少次都无关紧要)

2. 您可以从起点出发，参观完所有目标后返回基地。

3. 您可以多次访问每个目标。

问题:

1) 我应该使用什么算法来解决这个问题？

2)我提出的方法

假设目标 = [A, B, C]

• 我正在考虑使用 Dijkstra 算法找到到达任何目标的最短路径。
• 到达目标后，我会使用 Dijstra 找到任何剩余的目标。
• 找到所有目标后，我将使用 Dijstra 找到返回起点的路径。
• 这应该给我找到所有目标并回家的最短路径

Answer 1

您走在正确的轨道上，但是您的问题已简化为旅行商问题 (TSP)。

使用您提到的 Dijkstra，您可以用一条边替换目标节点之间不包含任何目标节点的所有路径。结果是一个只有目标节点的图......这让你有了 TSP。

至于评论中的加权有向边，我认为只要边成本非负，Dijkstra 就完全没问题。