Priority queue and fibonacci queue/heap

Does anyone know whether the Dijkstra algorithm for finding shortest path in a graph can be implemented efficiently using non-destructive operations? The only implementation which I understand uses a mutable fibonacci heap to implement the REDUCE-MIN operation which seems inherently destructive to obtain O(1) complexity.

Yes, use a Brodal queue for your priority queue: https://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf

You can find an implementation at https://github.com/ruippeixotog/functional-brodal-queues

2 Likes

Similar discussion: How to reprioritize something in a priority queue