如何使用广度优先搜索来查找地图中的最短路径？

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,就可以保证路径长度最小.

An 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查找路径.