我正在阅读有关Graph算法的文章,我遇到了这两种算法.
我搜索了很多关于这个,但没有得到任何满意的答案!
我怀疑Dijkstra算法和BFS在寻找最短路径时有什么区别？
使用BFS在图表中查找最短路径我们所做的是
我们发现所有连接的顶点,将它们添加到队列中,并保持从源到该顶点的距离.现在,如果我们找到从源到该顶点的路径,距离更远,那么我们更新它!
这与Dijkstra算法中的完全相同!然后Dijkstra和BFS有什么区别？那么为什么这些算法的时间复杂度如此不同？
如果有人可以借助伪代码解释它,那么我将非常感激!
我知道我错过了什么!请帮忙!
Tim*_*lds 84
广度优先搜索只是Dijkstra算法,所有边权重等于1.
Dijkstra的算法在概念上是广度优先搜索,尊重边缘成本.
在两种情况下,探索图表的过程在结构上是相同的.
小智 5
Blockquote 在使用 BFS 在图中寻找最短路径时，我们所做的是发现所有连接的顶点，将它们添加到队列中，并保持从源到该顶点的距离。现在，如果我们找到一条距离更短的从源到该顶点的路径，那么我们更新它！
我们在 BFS 中不保持距离。它用于发现节点。所以我们把它们放在一个通用队列中并弹出它们。不像在 Dijikstra 中，我们将节点的累积权重（松弛后）放入优先队列并弹出最小距离。
所以 BFS 在等权重图中会像 dijikstra 一样工作，因为。
复杂度因使用简单队列和优先队列而异。