1

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?

10762409
  • 523
  • 4
  • 19
  • I think you need to better define what you're interested in. It's not necessary for either Djikstra or A* for the reason you mentioned: you can just use insertions. – IVlad Aug 22 '22 at 22:58
  • 2
    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. – Matt Timmermans Aug 22 '22 at 23:55
  • @MattTimmermans Thanks, that would answer my question - if you copy that into an answer I'll mark it as accepted; otherwise I'll copy it as an answer myself. – 10762409 Aug 23 '22 at 00:35

1 Answers1

2

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.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87