多源多目的地最短路径

loading...


0

假设我们有一个迷宫,宽度为W,高度为H.在这个迷宫中有多个人和多个塔 . 人是源(S),塔(D)是目的地 . 应该知道,我们对迷宫有一个全知的观点 . 我的问题是:

如果我想找到任何不同SD组合之间的最短路径,我该如何解决这个问题?

首先,我可以想到一个天真的解决方案,涉及将其分解为SD不同的OSOD操作,问题是这非常耗时 .

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

我需要一个可以在O(WH)时间内执行寻路的算法 . 我无法找到任何能够在O(WH)时间内获得最短路径且基于MSMD的路径 . 希望有人可以指出我正确的方向 .

loading...

1回答

  • 3

    想象一个图形,包括迷宫以及迷宫外的起点和终点顶点,从起始顶点到每个S的边缘,以及从每个D到终点顶点的边缘 .

    现在广度优先搜索(因为没有权重)来找到从单一开始到单端的最短路径 .

    我说'想象'那个图,因为你实际上不需要构建它 . 这最终只是一个简单的广度优先搜索,只需稍加修改 - 从根级别的所有S节点开始,到达任何D时停止 .

评论

暂时没有评论!