
Boost : 
From: LieQuan Lee (llee_at_[hidden])
Date: 20020115 17:30:26
On Tue, 20020115 at 17:12, David Abrahams wrote:
>
>  Original Message 
> From: "Jeremy Siek" <jsiek_at_[hidden]>
>
> >
> > The only downside 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 DECREASEKEY operation now.
 LieQuan Lee (AKA: Rich Lee) Research Associate Open Systems Laboratory Phone: 18128553608 Computer Science Department Email: llee_at_[hidden] Indiana University Homepage: http://www.osl.iu.edu/~llee
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk