Re: [boost] BGL: dijkstra questions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 21:58:03

What about BFS? It looks to me as though a three-state color map is totally
unneeded there. The way the algorithm is written out, it checks for gray
vertices, but there's nothing in the if/else clauses. Am I confused again?

----- Original Message -----
From: "David Abrahams" <david.abrahams_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, January 15, 2002 8:32 PM
Subject: Re: [boost] BGL: dijkstra questions

>
> ----- Original Message -----
> From: "Jeremy Siek" <jsiek_at_[hidden]>
> >
> > Yes, the coloring tells you whether the vertex is
> >
> > undiscovered, and not yet in the queue -> white
> > discovered, and in the queue -> gray
> > discovered, and out of the queue -> black
> >
> > so you know when to either insert into the queue or update a vertex
> > already in the queue.
> >
> > david.> Hmm, note that the queue must be made |E| big in my case. Still,
> you need a
> >
> > Right, so this would change the complexity of the algorithm from
> >
> > O((V + E) log V) to O((V + E) log E)
>
> Okay, I can see that I was missing at least a few things: you want to know
> if the vertex is gray, if you're going to avoid duplicate vertices in the
> Queue, since E can potentially be much larger than V in interesting
graphs.
>
> Anyway, since the user has to supply you with an IndexMap so that you can
> translate vertices to queue positions, you don't need a ternary color map.
> In fact, you don't need a separate color map at all. Just reserve two
values
> (say, -1 and 0) in the IndexMap to indicate the white and black nodes.
>
> Reducing the size of the queue just makes the case stronger for keeping
> distances and predecessors in the queue, at least if the user doesn't want
> to make a record of them.
>
> 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 != Ø)
>     t,u,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
>           if v in Q   // optimization - save space in Q if possible
>              RELAX(Q, (u, v, x + w(u,v)))  // replace path if shorter
>           else
>              INSERT(Q, (u, v, x + w(u,v))) // insert unconditionally
>       end for
>   end while
>
> This approach has all the same benefits I mentioned before, I think, and
it
> seems as efficient as what you currently do. I note that the distance and
> predecessor maps are only written once for each node. Putting them in the
> priority queue takes the place of that, but I would assume that frequent
> modifications all together in the priority queue improves locality.
> I might still be missing something, though.
>
> -Dave
>
>
>
> 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/
>
>