Hi guys,
I have been trying to implement the A* algorithm in C++ and would like to make use of the priority_queue structure to hold the open and closed lists of nodes. The problem is, all of the algorithms that I have found use the equivalent of a "search/contains" function to determine whether the priority queues contain a particular node. Unfortunately, the C++ priority_queue doesn't implement such a function :(
Could anyone suggest a good workaround or a useful alternative?
Thanks a lot!
The Boost Graph libraries have an implementation of A* (and Dijkstra if you want) which both rely on a priority queue implementation that has more capabilities than the standard priority queue. Their priority queue implementation is also indirect which is also helpful. It supports functions like push_or_update, update, and contains which is really all you need for A*, which is lacking from the standard implementation. This queue is called d_ary_heap_indirect and here is a simple example by daviddoria on using it (among other nice examples of BGL). There is also a slightly more feature-rich and non-BGL priority-queue implementation available in the latest version of Boost called just d_ary_heap.
And btw, checking if a node is in the open list by checking if it is present in the priority queue is really inefficient. Most algorithms rely on a coloring scheme (or masking) meaning that you store, for each node, a status flag (or color) which tells you whether the node is open or closed (or un-discovered, or inconsistent, etc, depending on the variation of A* that you are implementing). It's very easy, as part of your algorithm, to make sure that the state of the flag is consistent with what set or priority-queue the node is in, because you control when nodes are moved in and out of the sets. I encourage you to either use the BGL implementation of A* or to at least check it out, see it here: docs and code. I also have an implementation of AD* available which is in the same style as the BGL A*, available here.
Unfortunately for the work that I am doing I am not allowed to make use of the Boost Graph libraries. Do you have any other suggestions and perhaps some C++ specific code samples that I could take a look at?
Any help will be greatly appreciated :)
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.