多源多目标最短路径

Question

3

假设我们有一个迷宫，它的宽度为W，高度为H。在这个迷宫中，有多个人和多个塔。人是源（S），塔（D）是目的地。应该知道我们对迷宫有全知视角。那么我的问题是：

如果我想找到不同SD组合之间的最短路径，我该怎么做？

首先，我可以想到一种天真的解决方案，涉及SD不同OSOD操作的分解，但问题是这需要相当长的时间。

第二个选择是将其分解为S个不同的OSMD操作。但我怀疑这仍然对我所寻找的内容来说太低效了。

我需要一种算法，能在O(WH)的时间内执行路径查找。我还没有能找到任何能够以 O(WH) 时间复杂度执行最短路径查找并且基于MSMD的方法。希望有人能指点我正确的方向。

- erik p

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Timmermans · Accepted Answer

想象一下一个包括迷宫、起点和终点顶点（在迷宫外）的图表，从起始节点到每个S都有一条边，从每个D到终点顶点也有一条边。

现在使用广度优先搜索（因为没有权重）来查找从单个起点到单个终点的最短路径。

我说“想象”那个图表，因为你实际上不需要构建它。这最终成为了一个简单的广度优先搜索，进行了一些小的修改——你从所有的S节点开始，在达到任何D时停止搜索。