Dijkstra's shortest-path algorithm requires a priority queue with a decrease-key operation, as noted in the Wikipedia page and the C Boost Graph Library pseudocode.

Neither of these sources indicates whether the priority queue used in A* search requires the decrease-key operation (Wikpedia, C Boost). But the pseudocode in the Wikipedia article includes the line fScore[neighbor] := tentative_gScore h(neighbor), which seems like it would impact the ordering of elements in the priority queue.

I'm aware that technically, the decrease-key operation isn't necessary even in Dijkstra, with the same functionality achievable through just reinserting with the node with a lower key and keeping track of what vertices have been expanded. But is this necessary at all in A* search (assuming an admissible and consistent heuristic), i.e. if I don't want to re-insert nodes, do I have to implement the decrease-key operation?

CodePudding user response：

Dijkstra's algorithm is A* with a constant heuristic.

They are the same w.r.t the requirement for decrease-key -- you need decrease-key for the "standard" implementation, but it's common to get around that by re-inserting nodes.