运行 BFS vs Dijkstra 时间
Running Time of BFS vs Dijkstra
我有一个未加权的连通图 G，有 n 个顶点和 m 个边。
m=O(n log n).
我想找到从顶点s到顶点v的最短路径。
我想知道 BFS 遍历或 Dijkstra 算法是否渐近更快。
BFS 将从 s 开始。
Dijkstra算法，从s开始，实现斐波那契堆
BFS的运行时间为Θ(n+m) = O(n+n log n) = O(n log n)
而Dijkstra的运行时间为O(m+n log n) = O(n log n+n log n) = O(n log n)
对于这个问题，这两种算法的渐近速度都一样快，还是我遗漏了什么？
对于未加权图的给定属性：
- (,)相连，而
- || ∈ θ(||log||)
...对于 BFS 和带有斐波那契堆的 Dijkstra 算法，我们确实可以得出 (||) 的时间复杂度。
补充说明：
短语 “渐近一样快” 并不意味着存在输入大小，超过该输入大小两种算法都会 运行 一样快。这意味着对于足够大的输入，它们的 运行 宁时间（在同一台计算机上）的 比率 将保持在恒定的 min/max 范围内。
由于 Fibonacci 堆有相当多的开销，而 BFS 只需要一个简单的队列或两个数组，毫无疑问，这个有界比率将有利于 BFS。
我有一个未加权的连通图 G，有 n 个顶点和 m 个边。
m=O(n log n).
我想找到从顶点s到顶点v的最短路径。
我想知道 BFS 遍历或 Dijkstra 算法是否渐近更快。
BFS 将从 s 开始。 Dijkstra算法，从s开始，实现斐波那契堆
BFS的运行时间为Θ(n+m) = O(n+n log n) = O(n log n)
而Dijkstra的运行时间为O(m+n log n) = O(n log n+n log n) = O(n log n)
对于这个问题，这两种算法的渐近速度都一样快，还是我遗漏了什么？
对于未加权图的给定属性：
- (,)相连，而
- || ∈ θ(||log||)
...对于 BFS 和带有斐波那契堆的 Dijkstra 算法，我们确实可以得出 (||) 的时间复杂度。
补充说明：
短语 “渐近一样快” 并不意味着存在输入大小，超过该输入大小两种算法都会 运行 一样快。这意味着对于足够大的输入，它们的 运行 宁时间（在同一台计算机上）的 比率 将保持在恒定的 min/max 范围内。
由于 Fibonacci 堆有相当多的开销，而 BFS 只需要一个简单的队列或两个数组，毫无疑问，这个有界比率将有利于 BFS。