一尘不染

寻找最短路径时,BFS和Dijkstra算法之间有什么区别?

algorithm

我正在阅读有关图算法的文章,并且遇到了这两种算法。

我对此进行了很多搜索,但没有得到满意的答案!

我怀疑Dijkstra算法和BFS在寻找最短路径时有什么区别?

在使用BFS查找图中最短路径的同时,我们要做的是

我们发现所有连接的顶点,将它们添加到队列中,并保持从源到该顶点的距离。现在,如果找到从源到该顶点的距离更短的路径,那么我们将对其进行更新!

这与我们在Dijkstra算法中所做的完全一样!那么Dijkstra和BFS有什么区别?那么为什么这些算法的时间复杂性如此不同?

如果有人可以在伪代码的帮助下解释它,那么我将不胜感激!

我知道我缺少什么!请帮忙!


阅读 769

收藏
2020-07-28

共1个答案

一尘不染

广度优先搜索只是Dijkstra的算法,所有边缘权重等于1。

Dijkstra的算法从概念上讲是广度优先的搜索,它考虑了边缘成本。

在两种情况下,浏览该图的过程在结构上都是相同的。

2020-07-28