迪杰斯特拉的复杂性是正确的吗？

Question

我有一个关于Dijkstra算法运行时复杂性的问题。（参见CLRS vertion 3中的伪代码）：

DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← ∅ 
3 Q ← V[G]
4 while Q != ∅ 
5   do u ← EXTRACT-MIN(Q)
6   S ← S ∪ {u} 
7   for each vertex v ∈ Adj[u]
8     do RELAX(u, v,w)

我知道line3是O（V），line5总共是O（VlogV）；line7总共是O（E），line8意味着decrease_key（），所以每个Relax（）操作都是logV。但是在放松（）中，在d[v]之后

关于空间复杂性的问题：为了比较队列 Q 中的顶点，我设计了一个结构/类顶点，其中距离是一个成员，然后实现诸如运算符之类的

Answer 1

Dijkstra的算法（正如您所写的）没有运行时复杂性，除非您指定数据结构。你说的“第7行”与O（E）操作有关，这是对的，但让我们来看看这些行（幸运的是，Dijkstra“很容易”分析）。

> < li>

初始化意味着“给所有顶点一个无限的距离，除了源，其距离为0。非常简单，这可以在O(V)中完成。

这台电视机有什么用？你用它“只写”。

您将所有元素放入一个队列。这里有龙。什么是(优先级！)排队？一个数据结构，带有操作add，可选decrease key(Dijkstra需要)，remove(Dijkstra不需要)，extractMin。根据实现的不同，这些操作有一定的运行时间。例如，您可以构建一个哑PQ，它只是一个(标记)集-然后添加和减少一个键是恒定的时间，但为了提取最小值，您必须搜索。Dijkstra中的规范解决方案是使用一个队列(像堆一样)来实现O(log n)中的所有相关操作。让我们来分析一下这种情况，虽然从技术上来说斐波那契堆会更好。不要自己实现队列。通过使用一个真正的PQ实现，您可以节省多少，这是令人惊讶的。

你经历了n次循环。

每次，你提取最小值，这是O(n log n)总数(在所有迭代)。

这台电视机有什么用？

每个顶点的边最多经过一次，也就是说，每个边最多经过两次，因此，总的来说，无论循环O（e）次内发生什么，都要执行。

放松意味着检查您是否必须减少钥匙并这样做。我们已经知道，每个这样的操作都可以在队列中添加O（log V）（如果它是一个堆），并且我们必须做O（E）次，所以它是O（E log V），它主导着整个运行时间。

如果你拿一个斐波那契堆，你可以去O（VlogV E），但这是学术性的。实际实现调整堆。如果想知道实现的性能，请分析 PQ 操作。但正如我所说，如果你不完全知道你在做什么，最好使用现有的实现。你的想法“在调用reucateKey之前查找位置”告诉我，在你提出一个实现之前，你应该更深入地研究这个主题，这个实现有效地每个插入（通过排序每次调用一些reucrationKey）或O（V）每个提取Min（通过找到最小的按需）。