Lecture Outline for Week 12

I. A new all-pairs shortest path algorithm
	- let V be the number of vertices and E the number of edges
	- Dijkstra: O((V + E)logV) running time if using a good priority queue
		and an Adj. list (or O(V^2 + E) with Adj. Matrix)
		- fails on graphs with negative edge weights
	- Floyd-Warshall All-Pairs: O(V^3)
	- here is a new general all-pairs algorithm
		- will work on all graphs
		- will detect negative weight cycles
		- O(V^3 logV) running time

	- we will keep a sequence of VxV matrices, D^(m)
		- D^(m)[i][j] will store the shortest path from node i to node
		  j using at most m edges
		- let D^(1) = W where W is the weighted adjacency matrix
			W[i][j] = 0 if i = j
				  length(i,j) if (i,j) is an edge of graph
				  infinity otherwise
		- this D^(1) stores the length of the shortest path between
		  each pair of nodes using at most 1 edge
		- how to compute D^(m) from D^(m-1)
			- from previous discussion of all-pairs, if u->v is
			  the shortest path from u to v and if w is a node
			  on that path, then u->w is the shortest path from
			  u to w. 
			- let w be the vertex immediately preceding v on the
			  u->v path.  If u->v is a path of no more than m 
			  edges, then u->w is a path of no more than m-1 edges
		- so let us find the shortest u->v path of at most m edges, 
		  take the shortest path u->w of at most m-1 edges for all w,
		  and add the length of the (w,v) edge
		- D^(m)[i][j] = min {D^(m-1)[i][k] + W[k][j]} for 0<=k<n
		- here is some pseudocode
		Extend_Shortest_Path(D, W)
		{
		    let D' be a matrix of same dimensions as D
		    for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
			{
			    D'[i][j] = infinity
			    for (k = 0; k < n; k++)
				D'[i][j] = min(D'[i][j], D[i][k] + W[k][j])
			}
		}

		- note the above algorithm is a lot like matrix multiplication
			- replace infinity with 0, + with * and min with +,
			  and you have matrix multiplication
		- pseudocode for the whole algorithm
		All-pairs(W)
		{
		    D^(1) = W
		    for (i = 2; i <= n-1; i++)
			D^(i) = Extend_Shortest_Path(D^(i-1), W)
		}

		- let * indiceate a call to the Extend_Shortest_Path function
		- then the following is a trace of the algorithm:
			D^(1) = W
			D^(2) = D^(1) * W
			D^(3) = D^(2) * W
			...
			D^(n-1) = D^(n-1) * W
		- where n is the number of vertices
		- how far must we take the algorithm?
			- note that a shortest path can not traverse more than
			  n vertices and thus n-1 edges without having a cycle
			- thus, if there are no negative weight cycles,
				D^(n-1) = D^(n) = D^(n+1) = ....
			- we can modify the algorithm to test for negative
			  weight cycles by calculating D^(n) and testing
			  whether D^(n) < D^(n-1)
			- can you see why a negative weight cycle must decrease
			  the path for some pair of vertices in D^(n) ?
		- note that the current algorithm is O(V^4)
		- how to improve it?
			- repeated squaring
				- we wish to compute x^29
				- one method: x^29 = x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x
					- 28 total multiplications
				- another method:
					x^2 = x*x
					x^4 = x^2 * x^2
					x^8 = x^4 * x^4
					x^16 = x^8 * x^8
					x^29 = x^16 * x^8 * x^4 * x
				- total number of multiplications is 7
		- apply repeated squaring to the all-pairs algorithm
			D^(1) = W
			D^(2) = D^(1) * D^(1)
			D^(4) = D^(2) * D^(2)
			D^(8) = D^(4) * D^(4)
			....
			D^(2^(log n)) = D^(2^((log n) - 1) * D^(2^((log n) - 1)
		- since D^(n-1) = D^(n) = D^(n+1) = ..., we do not have to
		  compute the exact D^(n-1), we can repeat the algorithm to
		  the smallest power of 2 greater than n-1
		- then run the algorithm one more step to test for negative
		  weight cycles
		- why does this work?
			- consider the shortest path from u->v and the 
			  intermediate vertex w which is at the midpoint of
			  u->v
			- if u->v is a path of at most m edges, then u->w
			  is a path of at most m/2 edges and w->v is also
			  a path of at most m/2 edges
		- the resulting running time is O(V^3 logV)

II. Priority Queues
	- we have used these in event simulators and in Dijkstra's algorithm
	- definition: an abstract datatype in which each element has a priority
	  and the first out is the element with highest priority
	- possible implementations
		- use a linked list
			- insert: place item at head of list: O(1)
			- remove: search list for item of greatest priority
			  and remove that item: O(n)
		- use a sorted linked list
			- insert: place item into list in sorted order: O(n)
			- remove: remove item with highest priority: O(1)
		- use a heap:
			- insert: O(log n)
			- remove: O(log n)
			- if we are doing about the same number of each, this
			  will give a faster running time than the above 2
			  implementations
	- a heap can be implemented with a binary tree
		- how to implement a binary tree
			- as a linked structure: keep a link to each child
			  and parent
			- as an array: assume the array is indexed 1..n
				- root is A[1]
				- for node at A[i],
					- parent is A[i/2]
					- left child is A[2i]
					- right child is A[2i+1]
				- example:
					10
					/\
				       3  7
				      /\  /
				     1  2 5
				  stored as A = {10, 3, 7, 1, 2, 5}
	- how to implement the priority queue/heap
		- the heap property: every element has a equal or smaller 
		  priority as its parent
		- this the element with greatest priority will be at the root
		- important to keep the heap balanced and compact
		- to insert into the heap:
			- place item in next available spot and swap upward
			  until it is at the correct position (until priority
			  of element <= priority of parent)
			- at most log n swaps needed where n is # elements 
			  in heap
		- to remove from heap
			- remove the root
			- place the last item in the heap at the root and
			  swap down until it is at the proper location
			  (until its priority is >= the priority of both 
			   children)
			- if a node may swap with either child, it must always
			  swap with the child of greater priority
			- at most log n swaps needed

	Example: take above heap and remove maximum
                           5            7
            / \           / \          / \
           3   7   =>    3   7  =>    3   5
          / \ /         / \          / \
         1  2 5        1   2        1   2
	remove maximum again
                           2            5
            / \           / \          / \
           3  5    =>    3   5  =>    3   2
          / \           /            /
         1   2         1            1
	add 4
             5             5
            / \           / \
           3   2   =>    4   2
          / \           / \
         1   4         1   3