Dijkstra 的复杂性是否正确？

Question

我有一个关于 Dijkstra 算法的运行时复杂性的问题。（参见 CLRS 版本 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)

我知道第 3 行是 O(V)，第 5 行总共是 O(VlogV)；第 7 行总共是 O(E)，第 8 行隐含了 reduction_key() 因此每个 Relax() 操作的 logV。但是在relax()中，d[v]>d[u]+weight后决定放宽，在调用reduce_key(Q, pos, d[v] ) 用 d[v] 替换 pos 的键？请注意，此查找本身的成本为 O(V)。所以每个 Relax() 应该花费 O(V)，而不是 O(logV)，对吗？

关于空间复杂度的一个问题：为了比较队列 Q 中的顶点，我设计了一个结构体/类顶点，将距离作为一个成员，然后我实现了诸如 operator< 之类的操作，通过比较它们的距离来对顶点进行排序。但似乎我必须定义一个重复的数组 dist[] 才能在 Relax() 中执行 dist[v] = dist[u]+weight。如果我不定义重复数组，我必须在队列 Q 中查找 v 和 u 的位置，然后获取并检查它们的距离。它应该以这种方式工作吗？或者我的实现不好？

Answer 1

Dijkstra 的算法（如您所写）没有运行时复杂性，除非您指定 datastructures。您说“第 7 行”使用 O(E) 操作是正确的，但让我们来看看这些行（幸运的是，Dijkstra“容易”分析）。

1. 初始化意味着“给所有顶点一个无限的距离，除了距离为 0 的源点。很容易，这可以在 O(V) 中完成。

2. S 组有什么用？您使用它“只写”。

3. 您将所有元素放入队列。这里是龙。什么是（优先级！）队列？具有操作添加、可选地减少密钥（Dijkstra 需要）、删除（Dijkstra 中不需要）、extractMin 操作的数据结构。根据实现，这些操作有一定的运行时间。例如，您可以构建一个只是一个（标记）集合的哑 PQ - 然后添加和减少一个键是常数时间，但是为了提取最小值，您必须搜索。Dijkstra 中的规范解决方案是使用队列（如堆）在 O(log n) 中实现所有相关操作。让我们针对这种情况进行分析，尽管从技术上讲，斐波那契堆会更好。不要自己实现队列。使用真正的 PQ 实现可以节省多少成本，真是太神奇了。

4. 你循环了 n 次。

5. 每次，您都提取最小值，即 O(n log n) 总计（在所有迭代中）。

6. S 组有什么用？

7. 您最多通过每个顶点的边缘一次，即您最多对每个边缘进行两次加固，因此您总共执行循环 O(E) 次内发生的任何事情。

8. 放松意味着检查您是否必须减少一个键并这样做。我们已经知道每个这样的操作都可以在队列中添加 O(log V)（如果是堆的话），而且我们必须做 O(E) 次，所以它是 S O(E log V)，它支配了总运行时间.

如果你采用斐波那契堆，你可以下降到 O(VlogV+E)，但这是学术性的。实际实现会调整堆。如果您想了解您的实现的性能，请分析 PQ 操作。但正如我所说，如果您不完全知道自己在做什么，最好使用现有的实现。你的“在调用reduceKey之前查找位置”的想法告诉我你应该在提出一个实现之前深入研究该主题，该实现有效地每次插入需要O（V）（通过每次调用reduceKey时进行排序）或O（ V) 每个extractMin（通过找到需求的最小值）。