===========================================================================
CSC 373H               Tutorial Summary for Week  5             Winter 2006
===========================================================================

All-pairs Shortest Paths.  [Old CSC364 notes.]

  - Input: Directed graph G=(V,E) with arbitrary edge weights w(e),
        but no negative weight cycles.
    Output: For each pair u,v in V, weight of a "shortest" (smallest
        weight) path from u to v.

  - Greedy approach doesn't work: this would be Dijkstra's algorithm, which
    works fine for nonnegative weights but doesn't give the correct answer
    if any weights are negative.

  - Step 0:
    Consider a shortest path P from u to v.  Since G contains no cycle with
    negative weight, P must be simple (no cycles).  If P contains more than
    1 edge, let w be any intermediary vertex on P ("intermediary" means
    "other than the endpoints").  Let P_uw be the part of P from u to w and
    P_wv be the part of P from w to v.
    Claim:  P_uw is a shortest path from u to w.
    Proof:  By contradiction: suppose there is a path P' shorter than P_uw.
            If P' shares no intermediate node with P_wv, then P' followed
            by P_wv is a path from u to v shorter than P.
            If P' shares at least one intermediate node with P_wv, let z be
            the first such node; then the part of P' from u to z followed
            by the part of P_wv from z to v is a path from u to v shorter
            than P.
    Similarly, P_wv must be a shortest path from w to v.

    Only question is how to characterize subproblems?  Natural
    possibilities include limiting number of edges on path or limiting
    intermediary vertices allowed on path.  We choose to limit intermediary
    vertices since characterization of optimal substructure is based on
    considering intermediary vertices.

  - Step 1:  Define an array.
    Convention: refer to vertices by their index {1,2,...,n}.
        A[k,i,j] = smallest total weight of paths from i to j all of whose
        intermediate vertices come from {1,2,...,k}
    where i,j,k in {1,2,...,n}.

  - Step 2:  Write a recurrence.
    (Notation: "oo" is ASCII way to represent infinity symbol.)

        A[0,i,j] = 0       if i = j
        A[0,i,j] = w(i,j)  if i != j and (i,j) in E
        A[0,i,j] = oo      if i != j and (i,j) not in E

        A[k,i,j] = min{ A[k-1,i,j], A[k-1,i,k]+A[k-1,k,j] }
                (shortest i-j path using intermediary nodes from
                {1,2,...,k} either uses node k or it doesn't)

  - Step 3:  Compute values bottom-up.

    Trick: A[k,i,j] depends only on A[k-1,i,j], A[k-1,i,k] and A[k-1,k,j].
    Notice A[k,i,k] = A[k-1,i,k] and A[k,k,j] = A[k-1,k,j] for all i,j.
    This means we can avoid using full 3D array and instead update 2D array
    A[i,j] for values of k = 1,2,...,n without worry that values used for
    update are changing.

        for i := 1 to n:
            for j := 1 to n:
                if i = j:  A[i,j] := 0
                else if (i,j) in E:  A[i,j] := w(i,j)
                else:  A[i,j] := oo
        for k := 1 to n:
            for i := 1 to n:
                for j := 1 to n:
                    if A[i,k] + A[k,j] < A[i,j]:
                        A[i,j] := A[i,k] + A[k,j]

  - Step 4:  Find optimal answer.
    Each value A[i,j] updated up to n times.  Need to remember last value
    of k used to update A[i,j] using auxiliary array B[i,j].  Complete
    algorithm:

        for i := 1 to n:
            for j := 1 to n:
                if i = j:  A[i,j] := 0;  B[i,j] := -1
                else if (i,j) in E:  A[i,j] := w(i,j);  B[i,j] := 0
                else:  A[i,j] := oo;  B[i,j] := -1
        for k := 1 to n:
            for i := 1 to n:
                for j := 1 to n:
                    if A[i,k] + A[k,j] < A[i,j]:
                        A[i,j] := A[i,k] + A[k,j];  B[i,j] := k

        print_path(i,j):
            if B[i,j] = 0:
                print edge (i,j)
            else if B[i,j] > 0:
                print_path(i, B[i,j])
                print_path(B[i,j], j)
            // else either i = j or there is no path from i to j

  - Runtime?  Theta(n^3).

  - Example:  Arrays A and B for each value of k; to make easier to read,
    "oo" in A and "-1" in B are left blank.

    k = 0:       |  1  2  3  4             |  1  2  3  4
              ---+--------------        ---+--------------
               1 |  0       10           1 |           0
               2 |  1  0                 2 |  0         
               3 | 10  1  0              3 |  0  0      
               4 |           0           4 |            

    k = 1:       |  1  2  3  4             |  1  2  3  4
              ---+--------------        ---+--------------
               1 |  0       10           1 |           0
               2 |  1  0    11           2 |  0        1
               3 | 10  1  0 20           3 |  0  0     1
               4 |           0           4 |            

    k = 2:       |  1  2  3  4             |  1  2  3  4
              ---+--------------        ---+--------------
               1 |  0       10           1 |           0
               2 |  1  0    11           2 |  0        1
               3 | 10  1  0 12           3 |  0  0     2
               4 |           0           4 |            

    No further change for k=3 and k=4 (node 3 has no incoming edge, node 4
    has no outgoing edge).

    Call to print_path(3,4) yields following:
        print_path(3,4):
            print_path(3,2):
                print edge (3,2)
            print_path(2,4):
                print_path(2,1):
                    print edge (2,1)
                print_path(1,4):
                    print edge (1,4)
    final output = (3,2) (2,1) (1,4).