Deikstra with heap

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
dokov
New poster
Posts: 2
Joined: Fri Dec 03, 2004 5:30 pm

Deikstra with heap

Post by dokov »

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

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Post by nnahas »

the correct spelling is "Dijkstra 's algorithm." If you look it up in Google you'll see plenty of links.

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Post by cypressx »

int dijkstra(const vector<vector<int> > &graph,int source,int dest) {
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 .

eleusive
New poster
Posts: 9
Joined: Tue Sep 28, 2004 6:57 am
Location: United States

Post by eleusive »

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.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

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.
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.

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)

eleusive
New poster
Posts: 9
Joined: Tue Sep 28, 2004 6:57 am
Location: United States

Post by eleusive »

Ah, thank you for the clearup. As for time complexity, I am aware that it is O(mlogn), but the OP referenced an O(nlogn) solution so I was just trying to be consistant in illustrating the difference in the algorithms (although I was wrong about the vector<> not being used as a heap structure, as I myself had recieved the mis-information).

Post Reply

Return to “Algorithms”