在寻找最短路径时,广度优先搜索如何工作？

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的算法适应BFS,让您找到单源最短路径.

为了检索到一个节点从起点的最短路径,你需要保持两个项目在图中的每个节点:其当前的最短距离,并在最短的路径上一节点.最初所有距离都设置为无穷大,并且所有前驱都设置为空.在您的示例中,将A的距离设置为零,然后继续使用BFS.在每一步中,检查是否可以改善后代的距离,即从原点到前一个的距离加上您正在探索的边的长度小于当前节点的最佳距离.如果可以改善距离,请设置新的最短路径,并记住已获取该路径的前一个路径.当BFS队列为空时,选择一个节点(在您的示例中,它是E)并将其前任遍历回原点.这会给你最短的路径.

如果这听起来有点令人困惑,维基百科有一个很好的伪代码部分.

Answer 2

如上所述,如果出现以下情况,BFS 只能用于查找图表中的最短路径:

1. 没有循环

2. 所有边缘具有相同的重量或没有重量.

要找到最短路径,您所要做的就是从源开始并执行广度优先搜索,并在找到目标节点时停止.您需要做的唯一额外事情是有一个数组previous [n],它将为每个访问过的节点存储上一个节点.前一个源可以为null.

要打印路径,只需从源中直接遍历前一个[]数组,直到到达目标并打印节点.DFS还可用于在类似条件下查找图中的最短路径.

但是,如果图形更复杂,包含加权边和循环,那么我们需要更复杂的BFS版本,即Dijkstra算法.

Answer 3

从这里的教程

"它具有非常有用的特性,如果图中的所有边都未加权(或相同的权重),那么第一次访问节点是从源节点到该节点的最短路径"

Answer 4

我已经浪费了3天
最终解决的问题图
用于
找出最短距离
使用BFS

想分享经验.

When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges

#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)

#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path

#3
It does not matter what queue you use
   deque/queue(c++) or
   your own queue implementation (in c language)
   A circular queue is unnecessary

#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.

#5
Wikipedia BFS will work, and is sufficient.
    https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

我已经失去了3天尝试上述所有选择,一次又一次地验证和重新验证
它们不是问题.
(尝试花时间寻找其他问题,如果你发现上述任何问题5).

以下评论的更多解释:

      A
     /  \
  B       C
 /\       /\
D  E     F  G

假设上面是你的图形
图向下
为A,邻接是B&C
对于B,邻接是D&E
对于C,邻接是F&G

比如说,起始节点是A.

1. 当你到达A,to,B&C时,从A到B&C的最短距离是1

2. 当你到达D或E,到达B时,到A&D的最短距离是2(A-> B-> D)

类似地,A-> E是2(A-> B-> E)

另外,A-> F&A-> G是2

所以,现在代替节点之间的1个距离,如果它是6,那么只需将答案乘以6的
例子,
如果每个之间的距离是1,则A-> E是2(A-> B-> E = 1 + 1 )
如果每个之间的距离是6,那么A-> E是12(A-> B-> E = 6 + 6)

是的,bfs可以采取任何路径,
但我们正在计算所有路径

如果你从A到去Z,那么我们的旅行从A所有路径到中间我,而且以后还会有我们放弃所有但最短路径多路径,直到我,然后用最短路径继续前进到下一个J节点
,如果再从I到J有多条路径,我们只用最短的一个
例子,
假设,
A - >我有距离5
(STEP)假设,I - > J我们有多条路径,距离7和8,因为7是最短的
我们把A - > J取为5(A-> I shortest)+ 8(现在最短)= 13
所以A-> J现在是13
我们现在重复上面的(STEP)J - > K等等,直到我们得到到Z.

阅读这部分,2或3次,并在纸上画画,你一定会得到我说的,祝你好运

Answer 5

广度优先搜索始终会在未加权图中找到最短路径（对于加权图，请参阅 Dijkstra 算法）。该图可以是循环的或非循环的。伪代码如下。

请注意，以下伪代码使用队列来管理要访问的顶点。它还假设您有顶点对象，其中每个顶点都用

vertex {
    visited  = false
    distance = infinity
    name     = "anything unique" [or, "start_vertex"/"end_vertex"]
    children = [ ... ]
}

start_vertex下面是对名称为顶点的引用start_vertex

算法：

vertex {
    visited  = false
    distance = infinity
    name     = "anything unique" [or, "start_vertex"/"end_vertex"]
    children = [ ... ]
}