Re: [boost] Dijkstra proof

From: Raja R Harinath (harinath_at_[hidden])
Date: 2002-01-28 20:34:09

Hi,

"David Abrahams" <david.abrahams_at_[hidden]> writes:

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

If you're still looking for a proof ...  (In the notation below, I
use |V| for the size of set V.  So, the order notation should
actually read O((|V| + |E|) log |V|), but following the CLR book,
I'll just write it as O((V+E) log V) instead.)

---------

  - At worst, each edge goes into Q once.  Basically, the "if u not in
    S" ensures that the "for each vertex v in Adj[u]" executes only
    once for each vertex 'u'.  So, the worst case length of Q is |E|.

  - So, all operations INSERT, EXTRACT-MIN etc are O(log E).  Since
    E=O(V^2), O(log E) = O(log V^2) = O(2 * log V) = O(log V).  So,
    we can say the INSERT, EXTRACT-MIN etc are O(log V).

  - The loop executes |E| times, and there's an O(log V) operation
    always (the EXTRACT-MIN).  Hence this portion is O(E log V).

  - Then there's the 'u not in S' test, which can reasonably be
    performed in O(log V) time (O(1) isn't too hard either).  Anyway,
    this portion also runs O(E) times, and hence time is O(E log V),
    and so can be swallowed up into the previous expression.

  - the 'if' succeeds only a few times, once for each vertex u.  So,
    the body of 'if u not in S' is entered O(V) times.

Now, if you consider the overall execution of body of the 'if', it is
equivalent to the following nested loop:

  for each vertex u in G
    for each vertex v in Adj[u]
      if v not in S
        INSERT(...)

This set of nested for loops touches each of the "boxes" in an
adjacency list representation exactly once.  There are O(V + E) boxes
in an adjacency list representation (the array of list heads has O(V)
boxes, and each edge has 1 or 2 "boxes" in the linked lists, i.e. O(E)
boxes -- together O(V+E) boxes).  So, the time taken is O(V+E) times
the body of the loop, which is O(log V) in our case.

  - Hence, the body of the 'if' statement eventually takes 
    O((V+E) log V) time across all iterations of the 'while' loop.

So, eventually, we have that the algorithm takes 

    O(E log V) + O((V+E) log V) 

i.e, O((V+E) log V) time. 

-----------

Now, if we know that all the vertices are reachable from the source,
it is necessary to have at least |V| - 1 edges.  

  |E| >= |V| - 1
  |V| <= |E| + 1
  |V| = O(E)

Hence, the expression above simplifies to O(E log V).

-----------

- Hari
-- 
Raja R Harinath ------------------------------ harinath_at_[hidden]
"When all else fails, read the instructions."      -- Cahn's Axiom
"Our policy is, when in doubt, do the right thing."   -- Roy L Ash