假设我们有一个迷宫，宽度为W，高度为H.在这个迷宫中有多个人和多个塔 . 人是源（S），塔（D）是目的地 . 应该知道，我们对迷宫有一个全知的观点 . 我的问题是：
如果我想找到任何不同SD组合之间的最短路径，我该如何解决这个问题？
首先，我可以想到一个天真的解决方案，涉及将其分解为SD不同的OSOD操作，问题是这非常耗时 .
第二种选择是将其分解为S个不同的OSMD操作 . 但我怀疑这对我正在寻找的东西来说仍然太低效 .
我需要一个可以在O（WH）时间内执行寻路的算法 . 我无法找到任何能够在O（WH）时间内获得最短路径且基于MSMD的路径 . 希望有人可以指出我正确的方向 .
1 回答
想象一个图形，包括迷宫以及迷宫外的起点和终点顶点，从起始顶点到每个S的边缘，以及从每个D到终点顶点的边缘 .
现在广度优先搜索（因为没有权重）来找到从单一开始到单端的最短路径 .
我说'想象'那个图，因为你实际上不需要构建它 . 这最终只是一个简单的广度优先搜索，只需稍加修改 - 从根级别的所有S节点开始，到达任何D时停止 .