Today:

* an all-pairs shortest path for weighted graphs
* review of breadth-first search
* review of depth-first search

All-pairs shortest path
-----------------------

So far in the course we have always used adjacency list to represent
graphs.  Here we present an algorithm that uses an adjacency matrix to
get the shortest paths between every pair of nodes in a weighted
graph.

		       2
                a ---------- b
		|            |
	        |            |5
	       1|            |
		|            |   2
		d -----------c-------e
		      1

Here we put in a[i][j] the distance between i & j, where 
	a[i][i] = 0
	a[i][j] = INF, if there is no edge between i and j

for the above matrix we have:

	    a	b   c	d   e
	 +--------------------	
	a|  0   2   I   1   I		(I == infinity)
	b|  2   0   5   I   I
	c|  I   5   0   1   2
	d|  1   I   1   0   I
	e|  I   I   2   I   0


Lets think about what this matrix really tells us.  It has the MINIMUM
distance between two nodes if you traverse at most 1 edge.  How might
we use this to get the minimum distance by going 2 edges?  For
example, to find shortest path from a-c, we need to look at all paths
from a-c with two edges:

	a-b-c, a-d-c, a-e-c

we can make this regular by assuming an edge of zero length from a
node to itself.  Then, we have:

	a-a-c, a-b-c, a-c-c, a-d-c, a-e-c
	 0+I    2+5    I+0    1+1    I+2

The shortest path of length 2 between a and c, is thus the minimum
over all the sums above, i.e., min(I,7,I,2,I) = 2.

We can do this for all pairs by redefining matrix multiplication to be

	c[i][j] = MIN (a[i][k] + b[k][j])
                   k

In other words, instead of computing the sum of products, we compute
the min of sums.

Then if we square the adjacency matrix, we will have the minimum
distance between every pair of nodes for length 2 paths.  If we square
again, for length 4 paths, etc.

Carry out the above example:

Squaring (for length 2 paths):


	    a	b   c	d   e
	 +--------------------	
	a|  0   2   2   1   I		(I == infinity)
	b|  2   0   5   3   7
	c|  2   5   0   1   2
	d|  1   3   1   0   3
	e|  I   7   2   3   0

	Note:  We can't get from a-e in 2 steps, so a-e is still inf.
		b-c in only 2 steps, best can do is 5, but if we can
		take 3 we can get down to 4 as we see now:

and again (for length 4 paths):


	    a	b   c	d   e
	 +--------------------	
	a|  0   2   2   1   4		(I == infinity)
	b|  2   0   4   3   6
	c|  2   4   0   1   2
	d|  1   3   1   0   3
	e|  4   6   2   3   0

If we square again, will anything change?  No, since the maximum path
between two nodes is at most 4 edges. (i.e. N-1 edges for N nodes)

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

Breadth-first search
--------------------

0) Start the search at some node v.  Visit v.
1) Visit all nodes at distance 1 from v.
2) Visit all nodes at distance 2 from v.
...


Example:

  v --------- a
  |\          |\
  | \         | \
  |  \        |  b-----e
  |   \       | /
  |    \      |/
  c-----i-----d
  |           |\
  |           | \
  f-----------g--h
              |
              j
0) visit v
1) visit a, i, c
2) visit b, d, f
3) visit e, g, h
4) visit j

Algorithm:

  Label each node either 1) visited, 2) on fringe, or 3) unknown.
  Also, label each node with its distance from v.

  Initially, label all nodes except v "unknown".  Label v "on fringe", and
  put v in a queue.  Initially, give node v distance 0, give all other
  nodes distance infinity.

  The queue will hold all nodes labeled on fringe -- neighbors of
  visited nodes that have not themselves been visited.  Once a node
  enters fringe, its final distance is known.

  Remove nodes from the queue one at a time.

  When a node u is removed, label it visited.  Add any neighbors of u that
  are not visited and not on fringe to the queue.  Label
  the neighbors "on fringe", and give them distance dist(u)+1.

Back to our example:

Queue:

v     (remove v - a, i, c move to fringe)
0

aic   (remove a - b, d move to fringe)
111

icbd  (remove i - d already on fringe)
1122

cbd   (remove c - f moves to fringe)
122

bdf   (remove b - e moves to fringe)
222

dfe   (remove d - g, h move to fringe)
223

fegh  (remove f)
2333

egh   (remove e)
333

gh    (remove g - j moves to fringe)
33

hj    (remove h)
34

j     (remove j)
4

Notice that the nodes in the queue are always ordered by distance.
Also, notice that nodes are visited in order of distance from v:

v aic bdf egh j
0 111 222 333 4

C++ code: (You can skip this code by reminding them this is just like
assignement two when the buckets were queues.  The code for dfs is
more interesting since it differs from assignment 2 so save time for
it if you can.)

// Assumes adjacency list rep. similar to assignment 2
// Assumes v is vertex 0.

label[0] = ON_FRINGE;
dist[0] = 0;
for (i = 1; i < n; i++){
  label[i] = UNKNOWN;
  dist[i] = INFINITY;
}

Queue q;
q.insert(0);

while (q.length() > 0) 
{
  int current = q.remove();
  label[current] = VISITED;
  for(int i=0; i<aGraph->numNeighbors(current); i++) 
  {
	int neighbor = aGraph->getNeighbor(current, i);
	if (label[neighbor] == UNKNOWN) 
        {
	      label[neighbor] = ON_FRINGE;
	      dist[neighbor] = dist[current] + 1;
	      q.insert(neighbor);
	}
  }
}

Breadth first search tree: 

0               1
  v --------- a
  |\          |\
  | \         | \ 2     3
  |  \        |  b-----e
  |   \       |
  |1   \ 1    |2
  c     i     d
  |           |\
  |2          |3\ 3
  f           g  h
              |4
              j

Notice that this tree gives a shortest path from v to each node.


Depth-first search
------------------

* Replace the queue with a stack.
* Label nodes either VISITED or NOT_VISITED.
* Don't worry about distances.
* Allow a node to appear more than once on the stack.

Example:

  v --------- a
  |\          |\
  | \         | \
  |  \        |  b-----e
  |   \       | /
  |    \      |/
  c-----i-----d
  |           |\
  |           | \
  f-----------g--h
              |
              j

Stack:

v     (remove v, add a, i, c)
cia   (remove c, add f)
fia   (remove f, add g)
gia   (remove g, add d, h, j)
jhdia (remove j)
hdia  (remove h, add d again since it hasn't been visited)
ddia  (remove d, add b)
bdia  (remove b, add e)
edia  (remove e)
dia   (remove d - already visited, so don't add neighbors)
ia    (remove i)
a     (remove a)

Depth-first search tree:

  v --------- a
  |\
  | \
  |  \           b-----e
  |   \         /
  |    \       /
  c     i     d
  |            \
  |             \
  f-----------g--h
              |
              j


Another way of thinking about depth-first search:

Before visiting a node, recursively visit its children.

void dfs(int current)
{
  if (label[current] == VISITED) return;
  label[current] = VISITED;

  for(int i=0; i<aGraph->numNeighbors(current); i++) 
  {
	dfs(aGraph->getNeighbor(current, i));
  }
}

...

	// init the label array
	for (i = 0; i < n; i++)
	{
		label[i] = NOT_VISITED;
	}
	// call dfs
	dfs(0);


(Note: this will give a slightly difference DFS tree than the stack
algorithm gave.)