首页 文章

寻找多个点的最短路径

提问于
浏览 次
1

Requirements:

  • 您需要在图表上访问多个目标（无论您访问每个点的顺序或次数都无关紧要）

  • 您可以从起点开始，访问所有目标并返回基地 .

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

Question:

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

2）我提议的方法

我们说目标= [A，B，C]

  • 我正在考虑使用Dijkstra的算法来找到任何目标的最短路径 .

  • 一旦我到达目标，我使用Dijstra来找到任何剩余的目标 .

  • 一旦找到所有目标，我将使用Dijstra找到返回起点的路径 .

  • 这应该是我找到所有目标并回到家的最短途径

algorithm graph shortest-path

2 回答

  • 0

    您走在正确的轨道上，但您的问题会缩小为旅行商问题（TSP） .

    如上所述，使用Dijkstra，您可以使用单个边替换不包含任何目标节点的目标节点之间的所有路径 . 结果是一个只有目标节点的图表...这使您获得TSP .

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

    回复于
  • 0

    我认为这将是一个很好的近似值：

    Construct a Minimum Spanning Tree.

Do a pre-order traversal taking your source as the root.

Remove edges which are not necessary (removing which does not disconnect your source and targets).

    说这些是你的节点：

    enter image description here

    构建一个MST：

    enter image description here

    如果 a 是你的来源：做一个以root身份进行的预订遍历 .

    enter image description here

    移除不会断开目标和源的边缘 . （使用union-find很容易）

    回复于

相关问题