algorithm - 多源多目的地最短路径

Question

假设我们有一个迷宫，宽度为 W，高度为 H。在这个迷宫中有多个人和多个塔。人是源头 (S)，塔 (D) 是目的地。应该知道，我们对迷宫有无所不知的看法。那么我的问题是:

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

起初，我能想到一个天真的解决方案，涉及将其分解为 SD 不同的 OSOD 操作，问题是这非常耗时。

第二种选择是将其分解为 S 个不同的 OSMD 操作。但我怀疑这对于我正在寻找的东西来说仍然太低效了。

我需要一种可以在 O(WH) 时间内执行寻路的算法。我一直没能找到任何能在 O(WH) 时间内给我最短路径的东西，而且它是基于 MSMD 的。希望有人能为我指明正确的方向。

Answer 1

想象一个图，它包括迷宫以及迷宫外的开始和结束顶点，从开始顶点到每个 S 都有一条边，从每个 D 到结束顶点都有一条边。

现在广度优先搜索(因为没有权重)找到从单起点到单终点的最短路径。

我说“想象”该图，因为您实际上不必构建它。这最终成为一个简单的广度优先搜索，稍作修改——您从根级别中的所有 S 节点开始，并在到达任何 D 时停止。