Re: [boost] BGL: dijkstra questions

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