Re: [boost] BGL: dijkstra questions

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-15 12:58:49

On Tue, 2002-01-15 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 decrease-key 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 := EXTRACT-MIN(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 shortest-path *only* when the weight of all
edges is the same. The optimization is wrong when edges have different
weight.

-- 
Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    [phone]
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage: http://www.osl.iu.edu/~llee