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

Question

我正在使用广度优先搜索来查找图表中的位置，并且我很确定我的算法可以正常工作，但是当我完成后，我很难找到通往结果的最短路径。本质上，我可以使用 BFS 从我的开始位置到我的结束位置，但我不知道如何构建从结束到开始的最短路径。任何帮助，将不胜感激。

谢谢你。

Answer 1

一种选择如下。创建某种将每个节点与“父”节点相关联的方式（可能是哈希表，或者可能通过将“父”字段添加到代表节点的任何类型）。然后，每当您从队列中取出一个节点 u 并准备将一个节点 v 添加到队列中时，将 v 的父指针设置为节点 u。这标志着你到达节点 v 的方式是沿着通往 u 的路径，然后将路径延伸一条边到达 v。

完成此操作并完成 BFS 后，您可以通过从目标节点开始读取最短路径的反向，然后重复跟随父指针直到返回开始节点。一旦你有了这个，你可以反转这条路径来取回实际的最短路径。

希望这可以帮助！