Why does Dijkstra’s algorithm use decrease-key?

by

The reason for using decrease-key rather than reinserting nodes is to keep the number of nodes in the priority queue small, thus keeping the total number of priority queue dequeues small and the cost of each priority queue balance low.

In an implementation of Dijkstra’s algorithm that reinserts nodes into the priority queue with their new priorities, one node is added to the priority queue for each of the m edges in the graph. This means that there are m enqueue operations and m dequeue operations on the priority queue, giving a total runtime of O(m Te + m Td), where Te is the time required to enqueue into the priority queue and Td is the time required to dequeue from the priority queue.

In an implementation of Dijkstra’s algorithm that supports decrease-key, the priority queue holding the nodes begins with n nodes in it and on each step of the algorithm removes one node. This means that the total number of heap dequeues is n. Each node will have decrease-key called on it potentially once for each edge leading into it, so the total number of decrease-keys done is at most m. This gives a runtime of (n Te + n Td + m Tk), where Tk is the time required to call decrease-key.

So what effect does this have on the runtime? That depends on what priority queue you use. Here’s a quick table that shows off different priority queues and the overall runtimes of the different Dijkstra’s algorithm implementations:

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

As you can see, with most types of priority queues, there really isn’t a difference in the asymptotic runtime, and the decrease-key version isn’t likely to do much better. However, if you use a Fibonacci heap implementation of the priority queue, then indeed Dijkstra’s algorithm will be asymptotically more efficient when using decrease-key.

In short, using decrease-key, plus a good priority queue, can drop the asymptotic runtime of Dijkstra’s beyond what’s possible if you keep doing enqueues and dequeues.

Besides this point, some more advanced algorithms, such as Gabow’s Shortest Paths Algorithm, use Dijkstra’s algorithm as a subroutine and rely heavily on the decrease-key implementation. They use the fact that if you know the range of valid distances in advance, you can build a super efficient priority queue based on that fact.

Hope this helps!

More Related Contents:

  1. Negative weights using Dijkstra’s Algorithm
  2. graph – Dijkstra for The Single-Source Longest Path
  3. How to create the most compact mapping n → isprime(n) up to a limit N?
  4. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  5. Hash table runtime complexity (insert, search and delete)
  6. Data structures for loaded dice?
  7. Find kth smallest element in a binary search tree in Optimum way
  8. Find the shortest path in a graph which visits certain nodes
  9. How do you validate a binary search tree?
  10. design a stack such that getMinimum( ) should be O(1)
  11. Computing set intersection in linear time?
  12. Best algorithm to test if a linked list has a cycle
  13. Array remove duplicate elements
  14. What is the fastest way to find the closest point to a given point?
  15. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  16. insert, delete, max in O(1)
  17. Algorithm for autocomplete?
  18. How does Dijkstra’s Algorithm and A-Star compare?
  19. Hashing a Tree Structure
  20. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  21. How to restore the PriorityQueue to its initial state before the method call?
  22. Why is depth-first search claimed to be space efficient?
  23. Algorithm to simplify a weighted directed graph of debts
  24. Search a sorted 2D matrix [duplicate]
  25. Why are hash table expansions usually done by doubling the size?
  26. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  27. Algorithm for merging two max heaps?
  28. Why is vector array doubled?
  29. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment