Re: [boost] BGL: dijkstra questions

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-15 17:30:26

On Tue, 2002-01-15 at 17:12, David Abrahams wrote:
> 
> ----- 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 ;-)

I guess that you have come back to the DECREASE-KEY operation now. 

-- 
Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    [phone]
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage: http://www.osl.iu.edu/~llee