Boost logo

Boost :

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.> 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,
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.> 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
david.> INSERT(Q, (u, v, x + w(u,v))) // put the path in the queue
david.> end for
david.> end while
david.> Am I missing something, like the loss of some important event

||| At first glance, your algorithm makes sense to me. I like it. Let's do
||| 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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at