
Boost : 
From: Jeremy Siek (jsiek_at_[hidden])
Date: 20020115 15:46:28
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 decreasekey 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 := EXTRACTMIN(Q)
should the above line instead be
t,u,x := EXTRACTMIN(Q)
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.
Cheers,
Jeremy

Jeremy Siek http://php.indiana.edu/~jsiek/
Ph.D. Student, Indiana Univ. B'ton email: jsiek_at_[hidden]
C++ Booster (http://www.boost.org) office phone: (812) 8553608

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk