Easiest way of using min priority queue with key update in C++

by

Although my response will not answer the original question, I think it could be useful for people who reach this question when trying to implement Dijkstra algorithm in C++/Java (like myself), something that was comment by the OP,

priority_queue in C++ (or PriorityQueue in Java) do not provide a decrease-key operation, as said previously. A nice trick for using those classes when implementing Dijkstra is using “lazy deletion”. The main loop of Dijkstra algorithm extracts the next node to be processed from the priority queue, and analises all its adjacent nodes, eventually changing the cost of the minimal path for a node in the priority queue. This is the point where decrease-key is usually needed in order to update the value of that node.

The trick is not change it at all. Instead, a “new copy” for that node (with its new better cost) is added into the priority queue. Having a lower cost, that new copy of the node will be extracted before the original copy in the queue, so it will be processed earlier.

The problem with this “lazy deletion” is that the second copy of the node, with the higher bad cost, will be eventually extracted from the priority queue. But that will be always occur after the second added copy, with a better cost, has being processed. So the very first thing that the main Dijkstra loop must do when extracting the next node from the priority queue is checking if the node has being previously visited (and we know the shortest path already). It is in that precise moment when we will be doing the “lazy deletion” and the element must be simply ignored.

This solution will have a cost both in memory and time, because the priority queue is storing “dead elements” that we have not removed. But the real cost will be quite small, and programming this solution is, IMHO, easier than any other alternative that tries to simulate the missing decrease-key operation.

More Related Contents:

  1. How to get the maximum number after erasing n digits from the number [closed]
  2. LRU cache design
  3. what is the difference between set and unordered_set in C++?
  4. TMP: how to generalize a Cartesian Product of Vectors?
  5. Why would anyone use set instead of unordered_set?
  6. Order Statistic Tree in C++
  7. Mixing two arrays by alternating elements two by two
  8. Recursive and non-recursive traversal of three degree tree
  9. banker’s algorithm in c++
  10. What is the difference between palindrome permutation and permutation? [closed]
  11. Sorting zipped (locked) containers in C++ using boost or the STL
  12. Looking for C++ STL-like vector class but using stack storage
  13. Is there a way to access the underlying container of STL container adaptors?
  14. std::transform() and toupper(), no matching function
  15. C++ string::find complexity
  16. How to create a trie in c# [closed]
  17. what is “stack alignment”?
  18. Special simple random number generator
  19. Finding nearest point in an efficient way
  20. How can std::make_heap be implemented while making at most 3N comparisons?
  21. Writing a simple equation parser
  22. What is the right approach when using STL container for median calculation?
  23. Howto create combinations of several vectors without hardcoding loops in C++?
  24. How to rotate a N x N matrix by 90 degrees? [closed]
  25. Why there is no std::copy_if algorithm?
  26. LRU implementation in production code
  27. Calling erase with iterator vs const_iterator
  28. priority queue with limited space: looking for a good algorithm
  29. How can I test whether a number is a power of 2?
  30. Calculate mean and standard deviation from a vector of samples in C++ using Boost

Leave a Comment