algorithm - Dijkstra 算法 - 复杂度

Question

我在理解 Djisktra 算法的复杂性时遇到了一定的问题，希望有人能指正我。

在我的示例中，我采用了一个具有 n 个顶点的完整图。

您选择一个起始顶点，假设为 a1，标记它，然后计算边上的所有 n-1 个权重。 O(n)

您选择最小的一个。假设顶点 a2 并标记它。 O(n)

之后，您计算边上的 n-2 个新权重，并寻找下一个尚未标记的顶点以添加您的标记顶点集。

等等……

算法运行直到您可以标记所有顶点。复杂度:n-1 + n-2 + ... + n - (n - 1) = Binom(n,2) 这是 O(n^2)，而不是 O(n*ln(n)) 我想。

我多次读到人们使用堆进行优化，但我仍然看不出如何避免 Binom(n,2) 计算。

我一定是在某些时候错了，但看不出哪里错了。

Answer 1

如果你有一个完整的图，那么你当然不能比 O(n^2) 做得更好——因为，那是你输入的大小。

如果您没有完整的图，并且将边存储在邻接表中，那么您可以做得更好。您仍然需要查看所有边，但是使用优先级队列可以管理 O(e + n log n)，其中 e 是邻接列表中的边数。