使用二叉堆的 Dijkstra 时间复杂度

Question

令 G(V, E) 是一个具有正边权重的无向图。Dijkstra 的单源最短路径算法可以使用具有时间复杂度的二叉堆数据结构来实现：

 1. O(|V|^2)
 2. O(|E|+|V|log|V|)
 3. O(|V|log|V|)
 4. O((|E|+|V|)log|V|)

================================================== ======================

正确答案是——

4. O((|E|+|V|)log|V|)

================================================== ========================

我的方法如下 -

O(V+V+VlogV+ElogV) = O(ElogV)

• O(V) 来初始化。
• O(V) 构建堆。
• VlogV 执行 Extract_Min
• ElogV 执行减少键

现在，当我得到 O(ElogV) 并且当我看到选项时，我的一部分说正确的是 O(VlogV) 因为对于稀疏图 |V| = |E|，但正如我所说，正确答案是 O((|E|+|V|)log|V|)。那么，我哪里出错了？

Answer 1

嗯，你是对的，复杂度实际上是O(E log V)。

由于E最大可达(V^2 - V)/2 ，因此这与O(V log V)不同。

如果每个顶点都有一条边，则V <= 2E，因此在这种情况下，O(E log V) = O( (E+V) log V)。这是通常的情况，对应于“正确”答案。

但从技术上讲，O(E log V)与O( (E+V) log V)不同，因为V中可能存在一大堆断开连接的顶点。然而，在这种情况下，Dijkstra 算法将永远不会看到所有这些顶点，因为它只找到连接到单个源的顶点。因此，当这两种复杂性之间的差异很重要时，您是对的，而“正确答案”则不是。