java - 寻找最短路径时，广度优先搜索如何工作？

Question

我做了一些研究，但我似乎遗漏了这个算法的一小部分。我了解广度优先搜索的工作原理，但我不明白它将如何让我到达特定路径，而不是仅仅告诉我每个节点可以去哪里。我想解释我的困惑的最简单方法是提供一个例子:

例如，假设我有一个这样的图表:

我的目标是从 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？

另外，请注意，我实际上并没有使用树，因此没有“父”节点，只有子节点。

Answer 1

从技术上讲，广度优先搜索 (BFS) 本身并不能让您找到最短路径，这仅仅是因为 BFS 不是在寻找最短路径:BFS 描述了一种搜索图的策略，但它并没有说您必须特别搜索任何东西。

Dijkstra's algorithm适应 BFS 让您找到单源最短路径。

为了检索从原点到节点的最短路径，您需要为图中的每个节点维护两项:其当前最短距离和最短路径中的前一个节点。最初，所有距离都设置为无穷大，所有前辈都设置为空。在您的示例中，您将 A 的距离设置为零，然后继续 BFS。在每一步中，您检查是否可以提高后代的距离，即从原点到前任的距离加上您正在探索的边的长度小于当前节点的最佳距离。如果您可以提高距离，请设置新的最短路径，并记住获取该路径的前一个路径。当 BFS 队列为空时，选择一个节点(在您的示例中，它是 E)并遍历它的前辈回到原点。这将为您提供最短路径。

如果这听起来有点令人困惑，维基百科有一个不错的 pseudocode section主题。