
Boost : 
From: David Abrahams (david.abrahams_at_[hidden])
Date: 20020115 16:55:37
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 := EXTRACTMIN(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
Find shortest paths to all vertices in the graph.
The queue stores triples (t,u,x) where t,u are vertices and x is a
distance. I have no proof of the complexity of this algorithm. Can
someone help with that? The BGL docs claim O((V + E) log V), or just
O(E log V) if all vertices are reachable from the source.
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 := EXTRACTMIN(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
Proof by induction that the correct distances and predecessors are
found:
vertices are in one of 3 categories:
found  v is in S
known  v not in S but Q contains a tuple u,v,z for some u,z
I'll abbreviate this as: "v is in Q"
unknown  all other vertices. Abbreviated as: "v is in Z"
a triple (u,v,x) in Q is also referred to as "a path in Q"
P(s,u) denotes the shortest path from s...u
d(s,u) denotes the length of that path
Invariant:
At the beginning of the Nth iteration of the loop
I. All successors of elements in S are either in S
or in Q
II. some 0...N1th furthest vertices from s are in S
III. For each outgoing edge(u,v) of a vertex in S, either:
A. v is in S
OR
B. Q contains a triple (a,b,l) s.t. b is on
P(s,v) and l = d(s,b)
IV. For all (u,v,x) in Q, x == d(s,u) + d(u,v)
It follows that at step N, after EXTRACTMIN, either:
u is already in S. The removal of t,u,x from
Q did nothing to change the invariant above
OR
(t,u) is in P(s,u), and x == d(s,u)
Suppose it weren't: since t is in S, Q contained (a,b,n) on P(s,u)
by IIIB. But then, n < x and we'd have retrieved (a,b,n) from the
queue instead.
So adding u to S doesn't break II.
To maintain I, outgoing edges (u,v) are added to Q.
***Here's where I prove the optimization is legal***:
If v is already in S, part I is trivially satisfied. we have also
satisfied part IIIA. and don't need to satisfy IIIB. We can skip
adding any paths to v. Since we haven't added anything to Q, IV is
still satisfied.
All other triples (u,v,x') are added to Q to satisfy I, where
x' == x + d(u,v)
IV is satisfied for each of these: since (t,u) is in P(s,u),
x == d(s,u), thus x' = d(s,u) + d(u,v)
IIIB is also satisfied. One of three cases:
1. if (t,u) was on P(s,v), then u was trivially on P(s,v). Either
u>v is on P(s,v) or one of u's other outgoing edges is. IIIB
is trivially satisfied, since all u's successors not in S were
added to Q.
2. (t,u) was not in P(s,v), but another path to v was already in Q
In that case, IIIB already had to be satisfied for v.
3. (t,u) was not in P(s,v), and (u,v,x') is the only path to v in
Q. Since all successors of elements in S are either already in
S or in Q, the shortest path from s to any vertex not in S must
go through a path in Q. So there must have been some triple
(a,b,l) in Q s.t. a>b is on P(s,v). Since v is reachable from
b, if a>b were not also part of P(s,b) it would form a subpath
of a cheaper path from s to v. By definition that is impossible.
Proof of base case:
When Q contains only (s,s,0), and S is empty,
1. there are no elements in S, so I is satisfied
2. S is 0 and N is 1, so II is satisfied
3. There re no outgoing edges of vertices in s, so III is satisfied.
4. The only element in Q is (s,s,0). d(s,s) + d(s,s) == 0
Whew!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk