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