Dijkstra proof

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 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 := 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

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

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...N-1th 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 EXTRACT-MIN, 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!