Boost logo

Boost :

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:    1-812-855-3608
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage:

Boost list run by bdawes at, gregod at, cpdaniel at, john at