CODEWITHSUNDEEP
algorithmdata-structuresbig-odijkstrafibonacci-heap
LoL
LoL

Reputation: 41

Dijkstra’s algorithm with a Fibonacci heap

I am trying to implement Dijkstra's algorithm for finding the shortest paths between nodes using Fibonacci Heap with Adjacency List representation for the graph. According to the algorithm I know, we have to find the minimum node in the Heap and then iterate through all its neighbours and update their distances. But to get the current distances of the neighbours(which is stored in each node in the heap), I have to find that particular node from the heap. 'Find' operation takes O(N) time where N is number of nodes in the Fibonacci Heap. So is my algorithm correct or am I missing something? Any help would be greatly appreciated.

Upvotes: 1

Views: 1445

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

An implicit assumption in a Fibonacci heap is that when you enqueue an element into the heap, you can, in time O(1), pull up the resulting node in the Fibonacci heap. There are two common ways you'll see this done.

First, you could use an invasive Fibonacci heap. In this approach, the actual node structures in the graph have extra fields stored in them corresponding to what the Fibonacci heap needs to keep things linked up the right order. If you set things up this way, then when you iterate over a node's neighbors, those neighbors already have the necessary fields built into them, which makes it easy to query the Fibonacci heap on those nodes without needing to do a search for them.

Second, you can have the enqueue operation on the Fibonacci heap return a pointer to the newly-created Fibonacci heap node, then somehow associate each node in the graph with that Fibonacci heap node (maybe store a pointer to it, or have a hash table, etc.). This is the approach I took when I coded up a version of Dijkstra's algorithm that uses Fibonacci heap many years back.

Upvotes: 0

Related Questions