stl dijkstra

[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]

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.

[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]

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!

[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]

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!

[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]

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

[mf]

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]

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.