如何在 Dijkstra 算法的最小优先级队列中 "decrease priority"？

Question

Wikipedia of Dijkstra's algorithm 有以下伪代码，它使用最小优先级队列：

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                           // Initialization
3
4      create vertex priority queue Q
5
6      for each vertex v in Graph:          
7          if v ≠ source
8              dist[v] ← INFINITY                 // Unknown distance from source to v
9              prev[v] ← UNDEFINED                // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                      // The main loop
15         u ← Q.extract_min()                    // Remove and return best vertex
16         for each neighbor v of u:              // only v that are still in Q
17             alt ← dist[u] + length(u, v)
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev

但是，不清楚decrease_priority如何在对数时间中实现。有人愿意帮忙吗？

Answer 1

这取决于您使用的数据结构，但是 decrease_priority 可以通过使用最小堆以 O(log n) 时间复杂度来实现。例如，我有以下堆：

如果我想把节点 i=8 的优先级从 25 降低到 1，我先改变它的优先级值，但是我仍然需要重新堆化以维护堆属性 (root < = 儿童）。这可以通过将该节点与其父节点交换直到达到堆属性来完成。这将最多进行 log n 次交换。

如何在 Dijkstra 算法的最小优先级队列中 "decrease priority"？

How to "decrease priority" in a min-priority queue in Dijkstra's algorithm?

priority-queue

dijkstra