Re: [boost] BGL: dijkstra questions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 20:32:59

----- 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