From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 17:03:17
----- Original Message -----
From: "Lie-Quan Lee" <llee_at_[hidden]>
> 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
> > 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 ;-)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk