
Boost : 
From: LieQuan Lee (llee_at_[hidden])
Date: 20020115 12:58:49
On Tue, 20020115 at 12:34, David Abrahams wrote:
> I know this will seem like a silly question to some; so much the better, the
> answer should be easy:
>
> I don't understand the reason for the decreasekey operation. I mean, I
> understand why it's needed the way that the algorithm is formulated, but
> AFAIK a formulation which stores the current weight of any path in the queue
> is far, far simpler and does the job:
>
> DIJKSTRA(G, s, w)
> for each vertex u in V
> d[u] := infinity
> p[u] := u
> end for
> INSERT(Q, (s,s,0))
> while (Q != Ã˜)
> u,t,x := EXTRACTMIN(Q)
> if u not in S
> d[u] = x // optional! d not needed for algorithm
> p[u] = t // also optional
> S := S U { u }
> for each vertex v in Adj[u]
> if v not in S // optimization  first path to v is always shortest
> INSERT(Q, (u, v, x + w(u,v))) // put the path in the queue
> end for
> end while
That algorithm yeilds a shortestpath *only* when the weight of all
edges is the same. The optimization is wrong when edges have different
weight.
 LieQuan Lee (AKA: Rich Lee) Research Associate Open Systems Laboratory Phone: 18128553608 Computer Science Department Email: llee_at_[hidden] Indiana University Homepage: http://www.osl.iu.edu/~llee
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk