Should I use mutable priority queue for dikjstra/A* algorithm?

Question

I am trying to implement A* algorithm and Dikjstra algorithm as a special case of A* (just pass h(x){return 0;} to A*), when choosing the priority_queue, I have two choices

1. use an empty priority_queue, and push start point when initializing, and do "pop u, push neighbors of u satisfying certain conditions", in this way, one node might be pushed twice if it is a common neighbor of two other nodes.
2. use a mutable priority queue that supports update()/decreaseKey()/increaseKey(), I could choose data structures in boost::heap or I could (actually I have) implement a priority_queue by myself, in this way, all nodes are needed to be pushed to the container when initializing and handles for them need to be kept.

what are the pros and cons of these two strategies and which one is more practical?

Answer 1

A common implementation of a priority queue for Dijkstra's in C++ uses std::set, where the smallest item is set.begin(), and you can find an exact item and erase it. You can also easily define a facade which allows to access std::set with a priority queue-like interface and support the additional update/erase/increaseKey/decreaseKey methods.

Look here for code samples for Dijkstra's implementations with both std::set and std::priority_queue: https://www.topcoder.com/community/data-science/data-science-tutorials/power-up-c-with-the-standard-template-library-part-2/#dijkstra2

This article also makes a claim, that the performance is naturally the same, whether you use std::priority_queue and discard stale items you've popped, or you use std::set and erase the old item immediately.