我做了一些研究，我似乎错过了这个算法的一小部分。我了解广度优先搜索的工作原理，但我不明白它究竟如何使我到达特定的路径，而不仅仅是告诉我每个节点可以去哪里。我想解释我的困惑的最简单方法是提供一个例子：
例如，假设我有一个这样的图表：
我的目标是从A到E（所有边缘都是未加权的）。
我从A开始，因为那是我的起源。我将 A 排入队列，然后立即将 A 排出队列并对其进行探索。这会产生 B 和 D，因为 A 连接到 B 和 D。因此，我将 B 和 D 都排入队列。
我将B排出队列并探索它，发现它通向A（已经探索过）和C，所以我将C排队。然后我把D排成一行，发现它通向我的目标E。然后我去排队C，发现它也会导致E，我的目标。
从逻辑上讲，我知道最快的路径是A->D->E，但我不确定广度优先搜索究竟如何帮助 - 我应该如何记录路径，以便在完成时，我可以分析结果并看到最短路径是A->D->E？
另外，请注意，我实际上并没有使用树，因此没有“父”节点，只有子节点。
从技术上讲，广度优先搜索（BFS）本身并不能让你找到最短路径，仅仅是因为BFS没有寻找最短路径：BFS描述了一种搜索图形的策略，但它并没有说你必须搜索任何特别的东西。
Dijkstra的算法调整BFS，让你找到单源最短路径。
为了检索从原点到节点的最短路径，您需要为图形中的每个节点维护两个项目：其当前最短距离和最短路径中的前一个节点。最初，所有距离都设置为无穷大，所有前置任务都设置为空。在您的示例中，您将 A 的距离设置为零，然后继续执行 BFS。在每个步骤中，您检查是否可以改善子体的距离，即从原点到前置任务的距离加上您正在探索的边的长度小于相关节点的当前最佳距离。如果可以缩短距离，请设置新的最短路径，并记住获取该路径的前置路径。当 BFS 队列为空时，选取一个节点（在您的示例中，它是 E）并将其前置任务遍历回源。这将为您提供最短的路径。
如果这听起来有点令人困惑，维基百科有一个关于这个主题的不错的伪代码部分。
如上所述，BFS只能在以下情况下用于查找图形中的最短路径：
没有循环
所有边缘的权重相同或没有权重。
要找到最短路径，您所要做的就是从源头开始，执行广度优先搜索，并在找到目标节点时停止。您唯一需要做的其他事情是有一个arraser[n]，它将存储访问的每个节点的上一个节点。源的上一个可以为空。
要打印路径，只需从源循环使用上一个[]数组，直到到达目的地并打印节点。DFS 还可用于在类似条件下查找图形中的最短路径。
但是，如果图更复杂，包含加权边和循环，那么我们需要一个更复杂的BFS版本，即Dijkstra的算法。
