Re: [boost] BGL: dijkstra questions

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-01-15 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 down-side 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: [phone]
----------------------------------------------------------------------