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

Question

Wikipedia of Dijkstra's algorithm has the following pseudocode, which uses a min-priority queue:

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

However, it's unclear how decrease_priority can be implemented in logarithmic time. Would anyone care to help?

Answer 1

It depends on which data structure you use, but decrease_priority can be implemented with O(log n) time complexity by using a min-heap. For example, I have the following heap:

If I want to decrease the priority of node i=8 from 25 to 1, I first change its priority value, but then I still need to re-heapify to maintain the heap property (root <= children). That can be done by swapping that node with its parent until the heap property is reached. This will take at most log n swaps.