BGL: dijkstra questions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 12:34:55

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

Look Ma:
    1. no color map (okay, you need a representation for S,
       but that's binary - dyn_bitset works if you want it)

    2. distance map is optional. If the user just wants to
       record predecessors, for example, there's no need to
       supply it. This is important as it either occupies
       lots of space or requires searching if it's sparse.

    3. if you don't care about predecessors, you can store
       a pair (vertex,cost) in the queue instead of a triple.

    4. Easier for users to understand - I'm having trouble
       figuring how to get what I want out of the BGL
       dijkstra. Okay, easier for /me/ ;-)

Am I missing something, like the loss of some important event points?

If not think you can do a similar thing for BFS, since that's just a
specialized DIJKSTRA:

BFS(G, s)
  for each vertex u in V
    d[u] := infinity
    p[u] := u
  end for
  PUSH_BACK(Q, (s,s,0))
  while (Q != Ø)
    u,t,x := POP_FRONT(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
          PUSH_BACK(Q, (u, v, x + 1)) // put the path in the queue
      end for
  end while

Note that even more optimizations apply: in this case you can just store a
single vertex descriptor in the queue if the user doesn't want predecessors
or distances...

...but I /have/ to be missing something. ?

-Dave

===================================================
  David Abrahams, C++ library designer for hire
 resume: http://users.rcn.com/abrahams/resume.html

        C++ Booster (http://www.boost.org)
          email: david.abrahams_at_[hidden]
===================================================