
Boost : 
From: David Abrahams (david.abrahams_at_[hidden])
Date: 20020115 17:03:17
 Original Message 
From: "LieQuan Lee" <llee_at_[hidden]>
> On Tue, 20020115 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.
Sort of. If you think of egdges in the queue it's the distance from s to the
source node plus the length of the edge. Whenever you pull something out of
the queue, if it's not already in S you've got its length.
> Well, it looks like you assume that the key of queue is the x value in
> your algorithm.
I'm not assuming. I know what I meant.
> 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.
What's still missing is a proof of the complexity. I'm sure the approach
used for proving the complexity of your Dijkstra would do just fine, but I'm
not going to attempt it. I only did this proof because I was afraid you were
right that it didn't work. Now I can use it ;)
Dave
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk