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:

You can find an implementation at


Similar discussion: How to reprioritize something in a priority queue