15-451 Algorithms                10/07/09

* All-pairs shortest paths
  - matrix method (recap from end of lecture)
  - Floyd-Warshall (didn't get to in lecture)

==========================
ALL-PAIRS SHORTEST PATHS
------------------------
Say we want to compute length of shortest path between *every* pair of
vertices.  If we use Bellman-Ford for all n possible starts S, this
will take time O(mn^2).  Here is a nice algorithm that uses the matrix
representation of a graph, and runs in time O(n^3 log n). 

ALL-PAIRS SHORTEST PATHS via MATRIX PRODUCTS
--------------------------------------------
Given graph G, define matrix A(G) as follows:
	- A[i,i] = 0 for all i.
        - if there is an edge from i to j, then A[i,j] = length of that edge.
	- otherwise, A[i,j] = infinity.

I.e., A[i,j] = length of shortest path from i to j using 1 or fewer edges.

Now, following the basic Dynamic Programming idea, can we use this to
produce a new matrix B where B[i,j] = length of the shortest path from
i to j using 2 or fewer edges? 

Answer: yes.  B[i,j] = min_k (A[i,k] + A[k,j])
[think about why this is true]

I.e., what we want to do is compute a matrix product B = A*A except we
change "*" to "+" and we change "+" to "min". 

In other words, instead of computing the sum of products, we compute
the min of sums.  What if we now want to get shortest paths using 4 or
fewer edges?  Just need to compute C = B*B.  I.e., to get from i to j
using 4 or fewer edges, we need to go from i to some k using 2 or
fewer edges, and then from k to j using 2 or fewer edges.

Just need to keep squaring O(log n) times.

Running time: O(n^3 log(n)).  Need to do log(n) matrix multiplies to
get all paths of length n or less and standard matrix multiply takes n^3
operations.

==============================================================================
All-pairs shortest paths via Floyd-Warshall.

Here is an algorithm that shaves off the O(log n) and runs in time
O(n^3).  The idea is that instead of increasing the *number* of edges in
the path, we'll increase the set of vertices we allow as intermediate
nodes in the path.  In other words, starting from the same base case
(the shortest path that uses no intermediate nodes), we'll then go on
to the shortest path that's allowed to use node 1 as an intermediate
node.  Then the shortest path that's allowed to use {1,2} as
intermediate nodes, and so on.

Let A be the same adjacency matrix for the graph we used earlier
(A[i][j] = length of edge (i,j) if the edge exists, infinity if it
doesn't exist, and 0 on the diagonal.)

/*  after each iteration of the outside loop, A[i][j] = length of
    shortest i->j path that's allowed to use intermediate vertices in
    the set 1..k  */ 

   for k = 1 to n do:
     for each i,j do:
       A[i][j] = min( A[i][j], (A[i][k] + A[k][j]);

i.e., you either go through k or you don't.  Total time is O(n^3).

What's amazing here is how compact and simple the code is!
===================================================================