ENHANCED HEAP FOR DIJKSTRA'S ALGORITHM

Abstract Success of min heap is because of its typical structure with parents containing values smaller than their children which makes them faster for sorting n elements in n time. This motivated Dijkstra to implement its ‘single source shortest path’ algorithm using min heap. However, one drawback of the min heap is its self-destructive nature that has been used in the algorithms of heapsort and priority queues. There is one variant of heap known as Fibonacci heap which is best suited for Dijkstra’s algorithm. In the case of the heapsort algorithm, the elements are removed from the min heap one by one which destroy the min heap making it impossible to perform any operation on it which restricts Dijkstra’s algorithm in detecting a negative weight cycle. The self-destructive nature of min heap inspired to introduce a novel structure named as Enhanced Heap to resolve the issue of self-destruction without any extra overhead.