Re: [boost] BGL: dijkstra questions

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-15 16:04:06

On Tue, 2002-01-15 at 15:50, David Abrahams wrote:

> 
> I just spent the last three hours writing a proof to refute Rich's assertion
> that it doesn't work. Well, it's almost done and it will be good for the
> docs. I'll send it to you.
> 

I think that in your first mail about that algorithm, you did not
mention the key of the queue. And it is not clear to me what the the key
of queue is.  My first respone in my mind of the key for the queue is
distance of vertices.

Well, it looks like you assume that the key of queue is the x value in
your algorithm. I also tried to come out a proof (either it is wrong or
right). We need a mathematical proof for that anyway if it is right.

-- 
Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    [phone]
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage: http://www.osl.iu.edu/~llee