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 执行 Decrease Key。

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

- Geeklovenerds

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算法时，它永远不会看到所有那些顶点，因为它只找到与单个源相连的顶点。因此，在这两个复杂度之间的差异很重要时，你是对的，“正确的答案”就不再正确了。

- Matt Timmermans

---

谢谢你，亲爱的Matt。 - Geeklovenerds

我不明白为什么答案不是 O(V + E logV)。我已经问过，但没有得到令人满意的回复：https://math.stackexchange.com/questions/3683910/time-complexity-of-dijkstras-algorithm - martinkunev

@martinkunev，我认为你在那里得到的回应还不错，但我添加了一个可能更清晰的回应。 - Matt Timmermans

我同意@martinkunev的观点，更优化的实现可以为所有图形实现O(V + E log V)复杂度：V步骤用于将距离初始化到所有顶点；然后仅从那里插入或更新已到达的节点。如果您的图形完全断开，则只需执行O(V)工作。如果您的图形完全连接，则需要执行O(E log V)工作。因此，对于所有可能的图形，O(V + E log V)。确实，通过使用最初为空的已到达顶点哈希表，可以将其减少到所有图形的O(E log V)，因此您不必立即初始化所有V个顶点的距离。 - jschultz410

Answer 2

这样说吧，正确答案是O((E+V)logV))。如果图的源顶点无法到达所有其他顶点，则VlogV可能大于ElogV。但是如果我们假设源顶点可以到达每个其他顶点，则图至少有V-1条边。因此，时间复杂度将为ElogV。这更多地与从源顶点可达性有关。

- BostonCommon