为何Dijkstra算法时间复杂度是O((V+E)logV)而非O((V+E)logE)

问题背景 #

假设我们有如下图形：

5               3
A ───────────► B ───────┐
│                       │
│                       │
│                       │
│                       ▼
└─────────────────────► C
           10

在此场景下，B和C都会被加入优先队列。当遍历B时，由于C是B的邻居，C会被再次加入队列。本质上每个顶点被加入队列的次数等于其入边的数量，最坏情况下优先队列可容纳E个元素，增删元素的代价为logE。结合遍历的O(V+E)代价，总复杂度似乎应为O((V+E)logE)，但所有教材及资料中均标注为O((V+E)logV)，这是为何？

同时，有资料提到logE与logV等价，因此总复杂度为O((V+E)logV)，请问logE与logV为何等价？

总复杂度标注为O((V+E)logV)的原因 #

渐近复杂度分析的核心是关注数量级的上限，而非精确的计算细节，我们可以从两个维度理解：

1. 边数的上限约束
   在无自环、无重边的简单图中，边数E的最大值为V(V-1)/2（完全图），此时E是O(V²)。代入对数可得：logE = log(O(V²)) = O(logV)——对数的常数因子和低阶项在渐近分析中会被忽略，因此logE的增长速度不会超过logV。

2. 有效操作的实际边界
   虽然每个顶点可能被多次加入优先队列，但当处理到某个顶点的旧条目（即该条目对应的距离不是当前已知的最短距离）时，我们会直接跳过后续的松弛操作。从全局来看，每条边最多只会触发一次有效的松弛操作，而优先队列的每次操作（插入/提取最小值）的代价，都可以用logV来界定——即便队列中存在E个元素，logE的渐近阶和logV完全一致。

logE与logV的渐近等价性 #

这里的“等价”指的是渐近复杂度意义下的同阶，即logE = Θ(logV)，证明如下：

• logE = O(logV)：
  对于连通图，E的最大值为O(V²)，此时logE = log(O(V²)) = 2logV + O(1)，常数因子不影响渐近阶；对于非连通图，每个连通分量的边数上限同样是该分量顶点数的平方，整体仍满足logE = O(logV)。

• logV = O(logE)：
  任何非空图中，若连通则E ≥ V-1，若不连通则每个连通分量至少有k-1条边（k为分量顶点数），整体E ≥ V - C（C为连通分量数），当V足够大时，E ≥ V/2，因此logV ≤ log(2E) = log2 + logE = O(logE)。

综上，logE和logV在渐近复杂度分析中属于同一阶，可以互相替换，因此O((V+E)logE)等价于O((V+E)logV)。

内容的提问来源于stack exchange，提问作者Aditya