Can someone tell mi the n*(log n) algorithm of Deikstra with heap. The one that is used for finding the shortest ways in a graph.

Excuse my english:P

## Deikstra with heap

**Moderator:** Board moderators

typedef pair<int,int> path;

priority_queue<path,vector<path>,greater<path> > q;

q.push(make_pair(0,source));

vector<bool> b(graph.size(),false);

while(!q.empty()) {

int w = q.top().first();

int u = q.top().second();

q.pop();

if(!b) {

if(u == dest) return w;

b = true;

FOR(e,graph.size()) if(graph[e] != -1)

q.push(make_pair(w+graph[e],e));

}

}

return -1;

}

it can be used as a pseudo code

where the priority_queue is the heap you can implement it how you want.I just have to say that this priority_queue<> sorts by q.first() and the a descending order. I hope it is clear ? IF not ask .

The priority_queue in his implementation IS actually a heap implemented using a vector (an array). More exactly, STL priority_queue is an adaptor, using an underlying data structure to store data and to implement a priority queue. By default priority_queue<T> is equivalent to priority_queue<T,vector<T>,less<T> >. In other words, cypressx only changed the order of elements in the priority queue.eleusive wrote:That implementation of Dijsktra's algorithm is not O(nlgn) since you are using a vector instead of a heap to store your data (it is O(n^2)). You can implement this correctly with a heap using the normal priority_queue data structure, but multiply all costs by -1 so that the heap is sorted correctly. Alternatively, you can define a state structure with an overloaded < operator. If you need me to post some code, please ask.

See e.g. http://www.sgi.com/tech/stl/priority_queue.html for more details.

The problem with the time complexity is only in the line

FOR(e,graph.size()) if(graph[e] != -1)

I.e. for each vertex you need to process all other vertices. You need to store a list of neighbors for each vertex and not just the distance matrix. Note that this can be conveniently done using a

vector< vector< pair<int,int> > > G

or even a

vector< list< pair<int,int> > > G

Also, eleusive, please be more exact when talking about the time comlexity. The time complexity of the fixed implementation would be O(M log N), where M is the number of edges (NOT vertices)