Dijkstra 时间复杂度说明

Question

对于使用最小堆优先级队列的 Dijkstra 实现，我将其设置为查找网络上不存在的站点，因此它必须检查所有内容。我的问题是，由于总体时间复杂度 O(V + E log V)，为什么网络找到到站点的最小距离所花费的时间在具有 500 个边缘和 400 个站点的网络上不存在，比具有 500 个边缘的网络更长和 500 个电台？

注：所有站点之间至少有一条边相连。用 |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

我想当你说

why is the time taken for a network to find locate the minimum distance to a station that does not exist on a network with 500 Edges and 400 Stations longer than one with 500 Edges and 500 Stations?

你并不是说对于任何一对具有规定数量的节点和边的图都是如此（因为它不是），而只是对于你构造和测试。

另一方面，时间复杂度语句给出了具有给定节点和边数的任何图实例的一般上限。换句话说，这是最坏的情况，即使对于算法最难快速处理的一个讨厌的图也是如此。

所以不矛盾。您只是碰巧选择了图实例，其中较小的图实际上使算法更难发现没有路径。不管这个例子如何，对于具有 400 个节点（和 500 条边）的最坏可能图，该算法仍然比具有 500 个节点（和 500 条边）的最坏可能图更快。

Answer 2

@Arne 是对的，这个问题在很大程度上取决于实际使用的图表。

|E| = |S|形成一个非常非常稀疏的图。我们举一个极端的例子。假设你有 |S| = 500，|E| = 500，所有节点整齐排列成一圈。在每次迭代中，算法会进行：

从优先级队列中取出一个节点。
跟随单边。
将单个节点添加到 PQ。

一直以来，PQ 运行接近于空。 PQ 是对常规队列的优化，但如果队列中只有一个节点，则没有太多可优化的地方。当您知道 N 始终为 1 时，就没有必要谈论 O(log N)。实际性能比 Big-Oh 符号预测的最坏情况性能要好得多。

现在添加 100 条边。算法突然有了选择！ PQ 填满。假设检查的第一个节点有 10 条边，因此 PQ 的大小为 10。它可能会在数十次迭代中保持此大小。 PQ 终于有一些工作要做了！这就是额外时间消耗的来源。

P.S。是Dijkstra，不是Djikstra

Dijkstra 时间复杂度说明

Dijkstra Time Complexity Clarification

python

graph

dijkstra

path-finding

shortest-path