1

我对 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)

我知道line3是O(V)，line5总共是O(VlogV)；line7 总共是 O(E)，line8 意味着 reduction_key() 所以 logV 对于每个 Relax() 操作。但是在relax()中，在d[v]>d[u]+weight之后决定放宽，我们不应该在调用reduce_key(Q, pos, d[v]之前查找队列Q中v的位置吗？ ) 用 d[v] 替换 pos 的键？请注意，此查找本身的成本为 O(V)。所以每个 Relax() 应该花费 O(V)，而不是 O(logV)，对吧？

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

4

1 回答 1

5

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

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

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

  3. 您将所有元素放入队列中。这里是龙。什么是（优先级！）队列？具有操作 add、可选的 reductionKey（Dijkstra 需要）、remove（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) 次，所以它是 O(E log V)，它支配了总运行时间.

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

于 2013-05-16T07:06:28.757 回答