Re: [boost] BGL: dijkstra questions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 17:12:05

----- Original Message -----
From: "Jeremy Siek" <jsiek_at_[hidden]>

>
> The only down-side I can see for this algorithm is that the queue can get
> a little bigger due to the same vertex showing up multiple times. However,
> since the queue insert/remove is logarithmic, I doubt that would have a
> significant effect. It will be interesting to compare execution times.

In your dijkstra, the same target vertex appears only once in the queue?
Hmm, note that the queue must be made |E| big in my case. Still, you need a
queue anyway. I guess data movement could be expensive. If you had a queue
with a hash table you could easily modify my algorithm to do the same thing:

Q is a priority queue of triples (u,v,x)
It has an associated hash table indexed on v so that when you do INSERT(q,
(u,v,x)):

    if (t,v,x') is in the queue for some t,x'
        if x < x'
            (t,v,x') is replaced with (u,v,x)
    else
        (u,v,x) is inserted

Wow, seems kinda complicated. I bet it's hard to win with this method.
Complicated code has a way of slowing things down ;-)

-Dave