Dijkstra的算法 - 复杂度

我有一个理解Djisktra算法的复杂性的问题，并希望有人能纠正我。Dijkstra的算法 - 复杂度

对于我的例子，我拍了一个有n个顶点的完整图。

您选择一个起始顶点，让我们说a1，标记它，然后计算边上的所有n-1权重。 O（n）

你挑最小的一个。假设顶点a2并标记它。 O（n）

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

依此类推...

该算法运行直到您可以标记所有顶点。复杂性：n-1 + n-2 + ... + n - （n-1）=在O（n^2）中的Binom（n，2），而不是O（n * ln（n））想。

我读过很多次人们使用堆进行优化，但是我仍然没有看到如何避免Binom（n，2）的计算。

我必须在某些时候是错的，但看不到在哪里。

2016-03-23 Imago

什么是n，为什么你必须在每个顶点做n次？ –

如果你有一个完整的图表，那么当然你不能做比O（n^2）更好的选择 - 因为这就是你输入的大小。

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

2016-03-23 18:22:07 comingstorm

好的。这让我非常沮丧，因为在所有的文献中，我只读到了你说的O（E + n + log n），这让我很困惑。我必须检查如何使用优先级队列。谢谢您的回答。 – Imago

完成与否，你仍然得到O（e + n log n）。只是当图完成时，e = n^2，给出O（n^2 + n log n）= O（n^2）。 –

回答