 # Boost :

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