I am implementing the A* path finding routines against a sparsely populated graph object. The algorithm appears to be fairly straight forward to implement. My question for the group though is how to implement the open and closed lists – specifically the open list.
In the implementation the open list needs to satisfy the following functionality: Find (and remove) the node with the most minimum F-Cost value stored in the list; be able to re-order the list in case an existing node’s F-Cost changes (i.e. a new route to the same node is cheaper); and, be able to find a specific node by name or ID value or whatever.
I have been reading up on the different structures and it seems that perhaps the STL data structure that most closely matches my needs is the Map. However, before I start coding, I wanted to ask the group here if there was perhaps a different data structure that they would recommend.