stl dijkstra
Moderator: Board moderators
stl dijkstra
Hi, ihave implemented dijkstra with my own heap, but i would like to know hot to do it with stl. The main problem is that if we use priority_queue, we dont have a method to change the priority of a particular element( decrease key operation) any sugestions?

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
There's no such method, you're right about it. If I really need it, I use std::map, but priority_queue is much faster, even if you insert elements again instead of changing their weight.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...
I usually code dijkstra in stl like this
Using priority queue  (queue in decreasing order)
I am not sure whether it is the perfect style of coding dijkstra in stl, but it works well...
Btw, binomial heaps are far better than fibonacci heaps, specially for dijksrta! But those things are not very easy to code!
Code: Select all
//dijkstra
while(!Q.empty()) {
Cow u=Q.top();
Q.pop();
int un=u.num;
if(cow[un].processed==true) continue;
if(u.dist > cow[un].dist) continue;
//print(u);
for(i=0; i<u.edge.size();i++) {
int v=u.edge[i];
if(cow[v].processed) continue;
if(cow[v].dist > u.dist + w[un][v]) {
cow[v].dist = u.dist+w[un][v];
Q.push(cow[v]);
}
}
cow[un].processed=true;
}
Code: Select all
bool operator>(Cow a,Cow b) {return a.dist<b.dist; }
bool operator<(Cow a,Cow b) {return a.dist>b.dist; }
priority_queue<Cow> Q;
Btw, binomial heaps are far better than fibonacci heaps, specially for dijksrta! But those things are not very easy to code!
fahim
#include <smile.h>
#include <smile.h>
What makes you say that?
AFAIK, fibonacci heaps are better for dijkstra (asymptotically) because they support decreasing a key value in constant amortized time (binomial is O(log n) ).
They are also substantially more difficult to code than the straightforward priorityqueue implementation (which uses a binary heap) which you gave.
AFAIK, fibonacci heaps are better for dijkstra (asymptotically) because they support decreasing a key value in constant amortized time (binomial is O(log n) ).
They are also substantially more difficult to code than the straightforward priorityqueue implementation (which uses a binary heap) which you gave.
Sorry quantris, I was wrong there ...
Using binomial heaps we can speed up dijkstra to O(ElogV), which considerably better running time only on very sparse graph. But fibonacci heaps gives O(VlogV+E), which is better for average graph... where V<E.
I am sorry that i have mistaken!
Using binomial heaps we can speed up dijkstra to O(ElogV), which considerably better running time only on very sparse graph. But fibonacci heaps gives O(VlogV+E), which is better for average graph... where V<E.
I am sorry that i have mistaken!
fahim
#include <smile.h>
#include <smile.h>
Binary vs Fibonacci
Hi
I tried to run dijkstra with binary and fibonacci heap also, but I could not construct graph which provide better running time with fibonacci. The binary heap implementation steps O(E*log(N)) but it cannot be slower than the fibonacci heap implementation. I tried with big graphs also.
The Radix heap on small integer costs is really fast. One time I would like to try also the relaxed heap but I do not have enough time to implement it.
Balazs
I tried to run dijkstra with binary and fibonacci heap also, but I could not construct graph which provide better running time with fibonacci. The binary heap implementation steps O(E*log(N)) but it cannot be slower than the fibonacci heap implementation. I tried with big graphs also.
The Radix heap on small integer costs is really fast. One time I would like to try also the relaxed heap but I do not have enough time to implement it.
Balazs
Hi deba,
I had the same idea before, until i found this.
Think for the worst kindof graph, we have V nodes and every nodes are connected to each other, therefore here E=V^2. Now our binomial heap gives the running time of O(E.logV) = O(V^2.logV), right ? Okay, now this is what fibonacci heap gives O(VlogV+E) = O(VlogV+V^2) = O(V^2) ; see, theoritically for the worst graph fibonacci heap gives us logV less effort. When you have something like 1000000 nodes (millions), fibonacci will be 20 times faster than our binomeal heap for the worst case! You didnt notice that because the big graphs that you made may be were not as worst as i just told you... if they were, you had to work with 1 million million edges!
Whatever, these are just theoritical hossposs, never mind! Binomeal works really cool, and unless we have an intergalactic graph or very large practical dataset, its useless to think about fibonacci heap.
Btw, I dont know radix heap
I had the same idea before, until i found this.
Think for the worst kindof graph, we have V nodes and every nodes are connected to each other, therefore here E=V^2. Now our binomial heap gives the running time of O(E.logV) = O(V^2.logV), right ? Okay, now this is what fibonacci heap gives O(VlogV+E) = O(VlogV+V^2) = O(V^2) ; see, theoritically for the worst graph fibonacci heap gives us logV less effort. When you have something like 1000000 nodes (millions), fibonacci will be 20 times faster than our binomeal heap for the worst case! You didnt notice that because the big graphs that you made may be were not as worst as i just told you... if they were, you had to work with 1 million million edges!
Whatever, these are just theoritical hossposs, never mind! Binomeal works really cool, and unless we have an intergalactic graph or very large practical dataset, its useless to think about fibonacci heap.
Btw, I dont know radix heap
fahim
#include <smile.h>
#include <smile.h>
Re: Binary vs Fibonacci
It is because of the big constant of fibonacci heap. Fibonacci heap has a much big constant factor and is harder to code, so i doubt wheater it is clever to implement it in dijkstra. I therefore am for the classic binary heap method.deba wrote:Hi
I tried to run dijkstra with binary and fibonacci heap also, but I could not construct graph which provide better running time with fibonacci. The binary heap implementation steps O(E*log(N)) but it cannot be slower than the fibonacci heap implementation. I tried with big graphs also.
The Radix heap on small integer costs is really fast. One time I would like to try also the relaxed heap but I do not have enough time to implement it.
Balazs