我正在阅读有关图算法的文章,并且遇到了这两种算法。
我对此进行了很多搜索,但没有得到满意的答案!
我怀疑Dijkstra算法和BFS在寻找最短路径时有什么区别?
在使用BFS查找图中最短路径的同时,我们要做的是
我们发现所有连接的顶点,将它们添加到队列中,并保持从源到该顶点的距离。现在,如果找到从源到该顶点的距离更短的路径,那么我们将对其进行更新!
这与我们在Dijkstra算法中所做的完全一样!那么Dijkstra和BFS有什么区别?那么为什么这些算法的时间复杂性如此不同?
如果有人可以在伪代码的帮助下解释它,那么我将不胜感激!
我知道我缺少什么!请帮忙!
广度优先搜索只是Dijkstra的算法,所有边缘权重等于1。
Dijkstra的算法从概念上讲是广度优先的搜索,它考虑了边缘成本。
在两种情况下,浏览该图的过程在结构上都是相同的。