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,
> if (t,v,x') is in the queue for some t,x'
> if x < x'
> (t,v,x') is replaced with (u,v,x)
> (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: 1-812-855-3608 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