c++ - 如何使用广度优先搜索在 map 中找到最短路径？

Question

为简单起见，假设我有图表:

O O P O |
O O O O O
O | O | O
O O O O O
A O O O O

其中我想使用广度优先搜索以最短路径从 A 行进到 P，其中由 | 指定的位置是禁区。我怎样才能达到这个结果？我一直看到广度优先搜索用于查找某个位置(在本例中为 P)，但我还没有看到任何用于存储路径距离和计算最短路径的实现(也没有有效的方法来存储以前访问过的位置和将它们排除在进一步审查之外)。此外，对于必然很大且需要大量推送和弹出的图形，通常建议使用什么队列？

Answer 1

广度优先搜索的美妙之处在于它会自动找到最短路径(你只需要在访问节点时跟踪你来自哪里)。使用广度优先搜索，成本最低的路径始终位于队列的开头，而成本最高的路径位于队列的末尾。一旦达到目标 P，就可以保证路径长度最短。

std::queue 是实现它的绝佳选择。

针对您的评论:您有一个节点/顶点队列(在您的例子中，这些是您的单元格)。当您访问一个节点时，您将之前未访问过的所有邻居添加到队列中。要跟踪您访问过哪些节点以及您的路径来自何处，请保留一个 std::array/std::vector wherefrom; ，每个元素一个你的节点。然后(伪代码!)

take element v from queue
 for each neighbour x of v
    if wherefrom[x] != NULL
     wherefrom[x] = v
     add x to end of queue

一旦你击中目标节点 P，你可以通过 wherefrom 回溯以找到路径。