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 终于有工作要做了!这就是额外时间消耗的来源。

附注这是 Dijkstra，不是 Djikstra。