我正在阅读有关Graph算法的文章,我遇到了这两种算法.
我搜索了很多关于这个,但没有得到任何满意的答案!
我怀疑Dijkstra算法和BFS在寻找最短路径时有什么区别？
使用BFS在图表中查找最短路径我们所做的是
我们发现所有连接的顶点,将它们添加到队列中,并保持从源到该顶点的距离.现在,如果我们找到从源到该顶点的路径,距离更远,那么我们更新它!
这与Dijkstra算法中的完全相同!然后Dijkstra和BFS有什么区别？那么为什么这些算法的时间复杂度如此不同？
如果有人可以借助伪代码解释它,那么我将非常感激!
我知道我错过了什么!请帮忙!
我在这里询问了一个最短路径算法: 2D航路点寻路:WP的组合从curLocation到targetLocation
(要了解我的情况,请阅读该问题以及此问题.)
似乎Dijkstra最短路径算法能够做到我需要的.但是,我的路线图中有大约500到1000个节点.
到目前为止,我所看到的实现将节点数限制在50以下.我的问题是:我是否应该使用Dijkstra最短路径算法,还是替代？Java中是否有任何实现？
java artificial-intelligence dijkstra path-finding graph-algorithm
Dijkstra 的运行时间为 O(|E| + |V|log|V|) 而暴力 BFS 的运行时间为 O(|E| + |V|)
那么为什么 Dijkstra 更优化呢？看起来它的运行时间更长。
编辑：请参阅标记的答案。事实证明，我在加权图上使用 BFS（基本上是暴力）对最短路径进行的运行时间分析是不正确的。在加权图上使用强力 BFS 的上限为 O(V!)。Dijstra 的更为优化。