CODEWITHSUNDEEP
c++algorithmdijkstra
NRK
NRK

Reputation: 111

Heap in Dijkstra algorithm

can someone explain whats the importance of HeapDesc in ShaneSaunders Dijkstra algorithm and how it is used here? In general i know how Dijkstra algorithm works. But, i din't get the heap part in implementation.

Its a big code. hence am posting a link if u want to have a look at it.

Here go's http://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.cpp

Upvotes: 0

Views: 2396

Answers (3)

Karthik T
Karthik T

Reputation: 31952

Dijkstra's algorithm involves a lot of "path of the lowest cost" lookup.

Min or max lookup is what a Heap is optimized for ( O(1) ), and this is why it is used.

As to HeapDesc itself, it just appears to be a factory method, used to allocate a Heap object. 

Heap *newInstance(int n) const { return new T(n); }; // from heap.h

Upvotes: 0

ipinak
ipinak

Reputation: 6039

HeapDesc probably implements the factory design pattern to create different kinds of Heaps. If you check the file http://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.h, you will notice that the heap variable in the constructor is an object of type Heap.

Take a look on this article for the factory design pattern. http://en.wikipedia.org/wiki/Factory_method_pattern

Upvotes: 1

mariosangiorgio
mariosangiorgio

Reputation: 5543

In Dijkstra you need an efficient data structure that provides you with the edge of minimum cost that allows you to reach another vertex.

Heap is exactly a data structure that allows you to store the set of edges and efficiently retrieve the one with minimum cost.

Upvotes: 1

Related Questions