stl dijkstra

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

stl dijkstra

Post by trulo17 »

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?

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

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

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris »

yes, usually I use priority_queue with a seperate array (or vector) to track the current priority of each element (so that I don't add unnecessary duplicates or process redundant entries), which usually works.

Someday I'll implement a good fibonacci heap and just use that.

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

I usually code dijkstra in stl like this

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;
    }
Using priority queue -- (queue in decreasing order)

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;
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! :cry:
fahim
#include <smile.h>

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris »

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 priority-queue implementation (which uses a binary heap) which you gave.

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

Sorry quantris, I was wrong there ... :oops:
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>

deba
New poster
Posts: 4
Joined: Tue Apr 18, 2006 9:36 am
Location: Hungary
Contact:

Binary vs Fibonacci

Post by deba »

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

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

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! :o

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 :oops:
fahim
#include <smile.h>

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

smilitude wrote:Think for the worst kindof graph, we have V nodes and every nodes are connected to each other, therefore here E=V^2.
In this worst case, simple O(V^2) Dijkstra, without heaps, will be faster.

brahle
New poster
Posts: 4
Joined: Mon May 22, 2006 11:39 am

Re: Binary vs Fibonacci

Post by brahle »

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

Post Reply

Return to “Algorithms”