
Boost : 
From: Jeremy Siek (jsiek_at_[hidden])
Date: 20020115 18:31:51
On Tue, 15 Jan 2002, David Abrahams wrote:
david.>
david.>  Original Message 
david.> From: "Jeremy Siek" <jsiek_at_[hidden]>
david.>
david.> >
david.> > The only downside I can see for this algorithm is that the queue can get
david.> > a little bigger due to the same vertex showing up multiple times. However,
david.> > since the queue insert/remove is logarithmic, I doubt that would have a
david.> > significant effect. It will be interesting to compare execution times.
david.>
david.> In your dijkstra, the same target vertex appears only once in the queue?
Yes, the coloring tells you whether the vertex is
undiscovered, and not yet in the queue > white
discovered, and in the queue > gray
discovered, and out of the queue > black
so you know when to either insert into the queue or update a vertex
already in the queue.
david.> Hmm, note that the queue must be made E big in my case. Still, you need a
Right, so this would change the complexity of the algorithm from
O((V + E) log V) to O((V + E) log E)
david.> queue anyway. I guess data movement could be expensive. If you had a queue
david.> with a hash table you could easily modify my algorithm to do the same thing:
david.>
david.> Q is a priority queue of triples (u,v,x)
david.> It has an associated hash table indexed on v so that when you do INSERT(q,
david.> (u,v,x)):
david.>
david.> if (t,v,x') is in the queue for some t,x'
david.> if x < x'
david.> (t,v,x') is replaced with (u,v,x)
david.> else
david.> (u,v,x) is inserted
david.>
david.> Wow, seems kinda complicated. I bet it's hard to win with this method.
david.> Complicated code has a way of slowing things down ;)
david.>
david.> Dave
david.>
david.>

Jeremy Siek http://php.indiana.edu/~jsiek/
Ph.D. Student, Indiana Univ. B'ton email: jsiek_at_[hidden]
C++ Booster (http://www.boost.org) office phone: (812) 8553608

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk