Re: [boost] BGL: dijkstra questions

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-01-15 15:59:23

On Tue, 15 Jan 2002, David Abrahams wrote:

david.> ||| At first glance, your algorithm makes sense to me. I like it. Let's do
david.> up
david.> ||| and implementation and play around with it. Similarly for BFS.
david.>
david.>
david.> @&#^%$(!!!!
david.>
david.> I just spent the last three hours writing a proof to refute Rich's assertion
david.> that it doesn't work. Well, it's almost done and it will be good for the
david.> docs. I'll send it to you.

Cool.

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.

Cheers,
Jeremy

----------------------------------------------------------------------
 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]
----------------------------------------------------------------------