Re: [boost] BGL: dijkstra questions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 13:35:08

Oh whoops:

> 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 should have been t,u,x

-Dave
----- Original Message -----
From: "David Abrahams" <david.abrahams_at_[hidden]>
To: <boost_at_[hidden]>
Cc: "Jeremy Siek" <jsiek_at_[hidden]>; "Lie-Quan Lee" <llee_at_[hidden]>
Sent: Tuesday, January 15, 2002 1:17 PM
Subject: Re: [boost] BGL: dijkstra questions

> Here I go, sticking my foot in my mouth... Maybe you can come up with a
> simple counterexample for me?
>
> I can't make this algorithm break (in my head).
>
> Further, by "the optimization" I assume you mean the line labelled "//
> optimization", yes? I don't see how that breaks anything, but even if we
> leave that out, I think all of the advantages remain.
>
> ----- Original Message -----
> From: "Lie-Quan Lee" <llee_at_[hidden]>
> To: <boost_at_[hidden]>
> Sent: Tuesday, January 15, 2002 12:58 PM
> Subject: Re: [boost] BGL: dijkstra questions
>
>
>
> 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
>
>
> Info: http://www.boost.org  Send unsubscribe requests to:
> <mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
>
>
>
> Info: http://www.boost.org  Send unsubscribe requests to:
<mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>