Re: [boost] BGL: dijkstra questions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 15:50:06

----- Original Message -----
From: "Jeremy Siek" <jsiek_at_[hidden]>
To: "boost" <boost_at_[hidden]>
Sent: Tuesday, January 15, 2002 3:46 PM
Subject: Re: [boost] BGL: dijkstra questions

On Tue, 15 Jan 2002, David Abrahams wrote:
david.> I know this will seem like a silly question to some; so much the
better, the
david.> answer should be easy:
david.>
david.> I don't understand the reason for the decrease-key operation. I
mean, I
david.> understand why it's needed the way that the algorithm is formulated,
but
david.> AFAIK a formulation which stores the current weight of any path in
the queue
david.> is far, far simpler and does the job:
david.>
david.> DIJKSTRA(G, s, w)
david.>   for each vertex u in V
david.>     d[u] := infinity
david.>     p[u] := u
david.>   end for
david.>   INSERT(Q, (s,s,0))
david.>   while (Q != Ø)
david.>     u,t,x := EXTRACT-MIN(Q)

||| should the above line instead be

||| t,u,x := EXTRACT-MIN(Q)

Yes, as posted earlier.

david.>     if u not in S
david.>       d[u] = x         // optional! d not needed for algorithm
david.>       p[u] = t         // also optional
david.>       S := S U { u }
david.>       for each vertex v in Adj[u]
david.>         if v not in S // optimization - first path to v is always
shortest
david.>           INSERT(Q, (u, v, x + w(u,v))) // put the path in the queue
david.>       end for
david.>   end while
david.>
david.>
david.> Am I missing something, like the loss of some important event
points?

||| At first glance, your algorithm makes sense to me. I like it. Let's do
up
||| and implementation and play around with it. Similarly for BFS.

@&#^%$(!!!!

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.

-Dave