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 )，其中e是邻接列表中的边数。