2

Dijkstra's shortest paths algorithm is O(E log V) when we re-insert nodes into the priority queue. However, if we use constant-time decrease_key, and Fibonacci heap is advertised for this, then the algorithm is O(V log V) because the main loop is not entered for every edge, only for every vertex. Is this possible in a purely functional setting? And how -- searching for the node to decrease key is already O(log n)? I have found on the internet that 2-3 finger trees can be used to implement amortized O(1) decrease_key, do Haskell's or OCaml's implementations support it?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
lukstafi
  • 1,883
  • 15
  • 22
  • 1
    Wikipedia alone knows the "2-3 heap" and the "Brodal queue", have you investigated these? Edit: Turns out the purely functional Brodal queue doesn't have constant time decrease-key, the Brodal & Okasaki paper lists it as future work. –  Jan 03 '14 at 12:48
  • @delnan I am asking out of curiosity, I have not studied the problem or even read the references yet. – lukstafi Jan 03 '14 at 14:17
  • Before you become too enamored with Fibonacci heaps, you should understand that that O(1) `decrease-key` comes with a fairly large constant. In addition, the simplicity of binary heaps makes the real-world running time faster than F-heaps except with very large data sets. See, for example, http://stackoverflow.com/a/508221/56778 – Jim Mischel Jun 01 '14 at 04:30

0 Answers0