python - Dijkstra 时间复杂度说明

Question

对于使用最小堆优先级队列的 Dijkstra 实现，我将其设置为查找网络上不存在的站，以便它必须检查所有内容。我的问题是由于整体时间复杂度 O(V + E log V) ，为什么网络查找到一个站点的最小距离所花费的时间在具有 500 个边和 400 个站点的网络上比具有 500 个边和 500 个站点的网络更长？
注意:所有站至少由 1 条边连接。带 |E| 的站= |S| + 100 有 100 个额外的边，这些边是唯一但随机连接的

#  PSEUDOCODE

1. INIT QUEUE & DICTIONARY WITH DISTANCE TO SOURCE BEING INF
2. ENQUEUE SOURCE WITH DISTANCE 0
3. SET DISTANCE TO SOURCE FOR SOURCE TO 0
4. LOOP WHILE QUEUE NOT EMPTY
      a. POP STATION FROM QUEUE (CALL IT P)
      b. IF P MARKED AS VISITED THEN RESTART LOOP (CONTINUE).
      c. IF P == TARGET RETURN DIST
      d. LOOP THROUGH ALL ADJACENT STATIONS (A) TO P
          i. IF (A IS NOT MARKED AS VISITED) AND (DIST TO P + DIST(P,A) < DIST TO A)
             1. CHANGE DIST TO A TO BE THE NEW DIST
             2. PUSH A ONTO THE PRIORITY QUEUE.

Answer 1

@Arne 是对的，这个问题很大程度上取决于所使用的实际图表。
|E| = |S|形成一个非常非常稀疏的图。我们举一个极端的例子。假设你有 |S| = 500, |E| = 500，所有节点整齐排列成一个圆圈。在每次迭代中，算法会进行:

从优先级队列中取出一个节点。

遵循单边。

将单个节点添加到 PQ。

一直以来，PQ 都在接近空运行。 PQ 是对常规队列的一种优化，但如果队列中只有一个节点，那么优化的空间并不多。当您知道 N 始终为 1 时，就没有必要谈论 O(log N)。实际性能比 Big-Oh 表示法预测的最坏情况性能要好得多。
现在添加 100 条边。突然间，算法有了选择! PQ 填满。假设检查的第一个节点有 10 条边，因此 PQ 的大小为 10。它可能会在几十次迭代中保持这个大小。 PQ 终于有工作要做了!这就是额外时间消耗的来源。
附言是迪克斯特拉，不是迪克斯特拉。