你能通过不完全填满优先级队列来提高 Dijkstra 的时间复杂度吗？
Can you impove Dijkstra's time complexity by not filling completely the priority queue?
你能通过不填满优先级队列来提高 Dijkstra 的时间复杂度吗？
我发现了两种不同的 Dijkstra 优先级队列方法。
时间复杂度不应该不同吗？
带优先队列的Dijkstra正常实现
您通常找到的 Dijkstra 最短路径的实现开始用所有顶点填充优先级队列：
（来自维基百科的伪代码：）
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
[...]
但是，如The Big O on the Dijkstra Fibonacci-heap solution中所述，Dijkstra最短路径算法的复杂度为：
O(|E| |decrease-key(Q)| + |V| |extract-min(Q)|)
使用二叉堆作为优先级队列等于：O((E + V)log(Q)) 因为 decrease-key(Q) 和 extract-min(Q) 都是 O(log(|Q|))
或者，如果您用所有顶点填充队列：O((E+V)log(V))
更快？带优先级队列的 Dijkstra 实现
然而，python 的 networkx 包中的实现并没有用所有顶点填充优先级队列。它仅从源顶点开始，并在发现其他顶点时继续插入它们。
类似于：
Q = priority queue
seen = provisional distances to every 'seen' vertex
add source to Q
seen[source] ← 0
while Q not empty:
v = pop(Q)
if v == target -> path found!
for neig in neighbours of v:
if neig not in seen:
add neig to Q
...
[normal Dijksta algorithm]
这样优先队列永远不会接近|V|元素（至少在相对稀疏的图中）。在任何给定点，所有顶点都位于已探索顶点和未见过顶点之间的边界内。与队列 (Q1) 的“正常”实现相比，此队列 (Q2) 的大小为：|Q2| = |Q1 where cost != inf|
我的问题
这是否意味着此实现的时间复杂度低于 O((E+V)log(V))？
我错过了什么吗？
我已经在道路网络图中对其进行了测试，确实以这种方式计算最短路径所需的时间更少。即使不包括在“正常”情况下填充队列初始值所花费的时间。
日志功能增长缓慢。即使在道路网络中，边界上可能有 n1/3 到 n1/2 个节点，日志因子仍然至少为 log n1/3 = (1/3) log n = Θ(log n)，因此您没有看到渐近节省。
特别是对于道路网络，有更重要的改进，例如覆盖范围和收缩等级。
是的，就实际运行时间而言，该算法更快。但是，complexity-wise，是一样的。为什么？我们可以先看一个极端：一个图有一个节点（起始节点），连接到大量节点（比如说 100），并且每个节点都连接到另一个节点（结束节点）。当遍历这个图时，你会在任何给定的时间将所有 100 个节点添加到优先级队列中，这几乎是图中的所有节点。然而，这种极端情况不太现实。然而，我们可以看一个更现实的案例：一个完全填充的二叉树。当您接近尾声时，优先级队列中将有 1/4 或 1/2 的节点（因为最后一行有一半的元素）。即使优先级队列中只有 sqrt(n) 个节点，log(sqrt(n)) 由于对数特性也只是 0.5*log(n)。因此，您只会得到常数因子变化，而不是渐近因子变化。
你能通过不填满优先级队列来提高 Dijkstra 的时间复杂度吗？
我发现了两种不同的 Dijkstra 优先级队列方法。
时间复杂度不应该不同吗？
带优先队列的Dijkstra正常实现
您通常找到的 Dijkstra 最短路径的实现开始用所有顶点填充优先级队列：
（来自维基百科的伪代码：）
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
[...]
但是，如The Big O on the Dijkstra Fibonacci-heap solution中所述，Dijkstra最短路径算法的复杂度为：
O(|E| |decrease-key(Q)| + |V| |extract-min(Q)|)
使用二叉堆作为优先级队列等于：O((E + V)log(Q)) 因为 decrease-key(Q) 和 extract-min(Q) 都是 O(log(|Q|))
或者，如果您用所有顶点填充队列：O((E+V)log(V))
更快？带优先级队列的 Dijkstra 实现
然而，python 的 networkx 包中的实现并没有用所有顶点填充优先级队列。它仅从源顶点开始，并在发现其他顶点时继续插入它们。 类似于：
Q = priority queue
seen = provisional distances to every 'seen' vertex
add source to Q
seen[source] ← 0
while Q not empty:
v = pop(Q)
if v == target -> path found!
for neig in neighbours of v:
if neig not in seen:
add neig to Q
...
[normal Dijksta algorithm]
这样优先队列永远不会接近|V|元素（至少在相对稀疏的图中）。在任何给定点，所有顶点都位于已探索顶点和未见过顶点之间的边界内。与队列 (Q1) 的“正常”实现相比，此队列 (Q2) 的大小为：|Q2| = |Q1 where cost != inf|
我的问题
这是否意味着此实现的时间复杂度低于 O((E+V)log(V))？
我错过了什么吗？
我已经在道路网络图中对其进行了测试，确实以这种方式计算最短路径所需的时间更少。即使不包括在“正常”情况下填充队列初始值所花费的时间。
日志功能增长缓慢。即使在道路网络中，边界上可能有 n1/3 到 n1/2 个节点，日志因子仍然至少为 log n1/3 = (1/3) log n = Θ(log n)，因此您没有看到渐近节省。
特别是对于道路网络，有更重要的改进，例如覆盖范围和收缩等级。
是的，就实际运行时间而言，该算法更快。但是，complexity-wise，是一样的。为什么？我们可以先看一个极端：一个图有一个节点（起始节点），连接到大量节点（比如说 100），并且每个节点都连接到另一个节点（结束节点）。当遍历这个图时，你会在任何给定的时间将所有 100 个节点添加到优先级队列中，这几乎是图中的所有节点。然而，这种极端情况不太现实。然而，我们可以看一个更现实的案例：一个完全填充的二叉树。当您接近尾声时，优先级队列中将有 1/4 或 1/2 的节点（因为最后一行有一半的元素）。即使优先级队列中只有 sqrt(n) 个节点，log(sqrt(n)) 由于对数特性也只是 0.5*log(n)。因此，您只会得到常数因子变化，而不是渐近因子变化。