# Boost :

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

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
>
> 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:    1-812-855-3608
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/
```