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