Per VognsenI wonder how often people who implement Dijkstra or A* pathfinding actually use the decrease_key-style approach for relaxing distances, as opposed to just inserting a duplicate with a smaller key. If you're implementing the priority queue with a binary/d-ary heap it requires additional space and/or time to be able to map node id -> heap index for decrease_key.
Jakob Hunsballe@pervognsen At some point on Hitman 5 we updated the priority (cost) but dequeueing was linear scan through all the active nodes (no min-heap or sorting) - what made a significant speed up was converting distances to 16 bit integers (float compare on the PS3 was somehow slow)