Lecture 11
Monday, June 12, 2017
11:10 PM
All-Pairs Shortest Paths
Given: Digraph  G=(V,E), where V={1,2,…,n},
             possibly negative costs  c(i,j),   BUT  no negative cycles! 
             ( c(i,j) = ∞  means no edge (i,j) in G )
Compute:  D(i,j) = cost of cheapest path from i to j,  for all i,j in V.   
Later, will also want an algorithm that, given (i,j), finds a cheapest path from i to j.
Observation:  Every cheapest path from i to j must be simple, i.e., with no cycles!
Floyd-Warshall DP algorithm
Step 1:  Array
Step 2: Recurrence
Step 3: Algorithm to fill in the array.
Step 4: Recover shortest paths from the array