So now let's compile the optimal substructure we just identified on all-pairs shortest paths into a dynamic programming algorithm and this would be the Floyed-Warshall Algorithm. Let me begin with a quiz and ask you to sort out the base cases. So remember our subproblems actually have three indices. The first index is the origin i, the second index is the destination j, and then there's our budget k which controls which of the vertices were permitted to use as internal nodes in a shortest path in the subproblem. So because of these three indices, we're going to be using a three-dimensional array A. So the plan, of course, is to solve systematically all of these subproblems where the subproblem corresponding to a choice of i, j, and k is just the length of the shortest path, starting at i ending at j, and using intermediate nodes only labeled 1 through k. And what's cool about these definitions is it's clear which are the bigger subproblems and which are the sub, smaller subproblems. That's controlled completely by the index k. So the smallest set of subproblems, the ones where we have to think through the base case is when k0. = 0. So the quiz asks you, how should we fill in A[i,j,0] for all of the various choices of origin i and the destination j? And as usual, if there are no feasible solutions. If no paths from i to j make use only of internal nodes 1 through k, then we define this to be plus infinity. Actually, the correct answer is c. So if i and j are the same, then, there is a path that starts at i ends at j, the empty path. It does in fact have no internal nodes at all and it has length: zero. [SOUND] Similarly if i and j are directly connected and we look only at paths that have no internal nodes whatsoever, well then, we're stuck with the cost of whatever the direct edge from i to j is, so we just fill it in with cij. On the other hand, if i is not equal to j, and i and j are not directly connected, then every path from i to j has at least one internal node, so there are no paths from i to j without any internal nodes. In that case, by definition, we assign a value of plus infinity. So having figured out the base cases, it's now a simple matter to write out the full blown Floyed-Warshall algorithm. In the past, I've been writing down a recurrence as an intermediate step. I think I'm going to skip that step here, we have so much practice with it. I think we can just jump straight to the code. And in the code, we will solve the problem systematically, from the smaller values of k to the bigger values of k. And each time we solve a subproblem, we are just going to do brute-force search amongst the two possibilities that we identified in the optimal substructure lemma. So we have our three-dimensional array A and it's three dimensional, because we have three indices for our subproblems. We gotta know what the origin is, we gotta know what the destination j is. And we gotta know how big a prefix k of vertices we have to work with for internal nodes in our paths. The base case [INAUDIBLE] was when K equals zero, so we just fill that in in a pre-processing step according to the quiz we just solved. And now we have our triple for loop. One for loop for each of the indices. Now, as always it's important, we solve the smallest subproblems first. The subproblem size is controlled by k so we better put k as the outermost for loop. The order of i and j is irrelevant, but k better go first. [SOUND] So to compute the value of a given subproblem, A, i, j, k, we just take the better, that is the minimum of the two candidates identified in our optimal substructure lemma. The first candidate furnished by k is one is just to inherit the solution computed in the last iteration of the outer for loop, that is i,j,k - 1. So the second candidate is provided by the second case of the optimal substructure lemma, this is where in the optimal solution to the current subproblem, we actually do use node k internally on the shortest path. In that case, we know what it has to look like, we have to just be taking the optimal solution from the last iteration of the outer for loop from i to k, and then catenating that with, that is adding to it the length of the shortest path computed last iteration of the outer for loop from k to j. So notice that our code does indeed pass the sanity check, you should always use when we evaluate a subproblem. We already have the solutions to all of the relevant subproblems available for constant-time lookup, that's because all of them were computed and the last interation of the outer for loop. There's also not a whole lot to say about the correctness or the running time. Correctness is the usual story. The only nontrivial work is in the optimal substructure lemma that identifies the only possible two candidates for the optimal solution to a subproblem. We're systemically solving all of them taking the better of the two only possible candidates. As far as the running time? Well, how many subproblems are there? Pretty easier to see, each of our three for loops takes on n different values, so that's n^3 subproblems overall. Pretty clear that we only do a constant amount of work per subproblem, that gives us the cubic running time. So, let me wrap up the discussion of Floyed-Warshall algorithm with a couple odds and ends, answers to two frequently asked questions. So question number one, which frankly I kind of hope you're wondering about, is well, what's up with the input graphs that do have a negative cost cycle? Let's recap what we've done. We stated and proved the optimal substructure lemma, only for input graphs that do not have a negative cost cycle. Our correctness argument for the Floyed-Warshall algorithm relied on the correctness of the recurrence, which in turn relies on the correctness of the optimal substructure lemma. So, if you feed in some arbitrary graph to the Floyed-Warshall algorithm, it might have a negative cost cycle, it might not. Well, the algorithm's just going to process its n^3 iterations and fill in this three-dimensional array either way. So you're left at the end of the day with this 3D array filled with numbers. And if it just so happened there was no negative cost cycle on the input graph, then, you know that the final batch of numbers when kN = n are, in fact, the correct shortest path distances. But how do you know if the input graph had a negative cycle or not? How do you know whether you can trust this last batch of numbers when k = n? Well, there's actually a very sleek answer to this question which is, all you need to do is scan the diagonal of the numbers computed in the final round. If the input graph does have a negative cost cycle, then for at least one vertex i, you will see a negative number in the entry A(i,i,n). So let's assume for the moment that this fact is true, that negative cost cycles will show up in diagonal in the final round of entries. Then, I hope it's clear how you can use the Floyed-Warshall algorithm to solve the general version of the all-pairs shortest paths problem. Whereby, the general version I mean, you're given an input graph, it may or may not have a negative cost cycle. And, you have to do one of two things, either you correctly deduce that the input graph has a negative cost cycle, then you're off the hook. Or, you compute correct shortest paths between all pairs of vertices. [SOUND] So the way you use that using Floyed-Warshall, you just take the input graph, you just run the algorithm, the n^3 iterations. You scan the diagonal. You scan A(i,i,n) for all values of i. If you see a negative number, you say, oop, I'm off the hook, there's a negative cost cycle. Sorry. [SOUND] And if the diagonal is all zeros, then you return the final batch of A(i,j,n) as the correct shortest path distances. I'm not going to prove this formally. I'll leave that for you to do in the privacy of your own home. But let me just suggest some intuition about why you would expect this to be true. So, suppose the input graph does, indeed, have a negative cost cycle. Pick some arbitrary vertex on that cycle, let's say a vertex x. Define vertex y to be the highest label of some other vertex on the cycle. Now, think about the following points in the Floyed-Warshall algorithm and its triple for loop. Think about when the outer iteration, the value of k is equal to y. So for the first time, the vertex y is eligible to be on internal nodes of shortest paths. And think of that in the inner for loops, when both i and j are equal to x. So, what is the recurrence or what is the formula the Floyed-Warshall is going to say? It's going to fill in this particular subproblem value, that is capital A(x,x,y) the minimum of two things. So first of all A(x,x,y - 1). Who knows what that is? But the second candidate, this is the interesting one, one candidate to fill in this entry will be A(x,y,y - 1) + A(y,x,y - 1). That is one of the candidates for the entry in this diagonal, A(x,x,y) will be the link of the shortest path from x to y whose all internal nodes are less than y plus the link of a shortest path from y back to x whose internal nodes are all less than y. Well, two candidates for such paths are the two halves of this cycle. Right y we chose to be the largest indexed node anywhere on the cycle, all the other vertices other than x and y have only smaller indices, so they are permissible internal nodes at the previous iteration. So if you take the sum of these two paths that's just a cycle length which by assumption is negative. So at this point in the Floyed-Warshall algorithm, if not earlier, when the outer for loop k is equal to y and when the looking from x back to x itself, at that point, we'll get a negative number. And because these numbers only go down in future iterations of the outer for loop, that negative number will persist to the end of the algorithm. That's why, to check for negative cycle, just scan the diagonal of the final batch of numbers that tells you whether or not there was one in the input graph. So, the second frequently asked question concerns reconstruction. Suppose after you run Floyed-Warshall, you actually want to know the actual sequence of edges that's the shortest path from some, your favorite origin i and your favorite destination j. So, like in the Bellman-Ford reconstruction solution, we're going to have to store a little bit of extra information, a constant amount of information per subproblem. Now, in the Bellman-Ford algorithm, we only had one subproblem per choice of desination, the source was fixed. And for each choice of a destination, we remembered the penultimate vertex on a shortest path to that destination. So for Floyd-Warshall, the number of subproblems is indexed by origins and destinations. And so, for each choice of an origin and destination, we're, again, going to remember some other vertex on a shortest path. But, the vertex we remember might not be the second to last one. It might not be the last top. Rather, what we're going to remember is the highest index vertex on a shortest path from i to j. So I'm going to call this additional information a two-dimensional array B, this is indexed just by the choice of the origin, by the choice of the destination. And again, the semantics is we want the i, j entry of this array to be the max label of any internal node on the shortest i, j path. So two things we have to understand are, first of all, how do we compute all these B(i,j) values on the forward-pass of the Floyed-Warshall algorithm without affecting its running time? Secondly, if we successfully compute all of these B(i,j) on the forward pass, how do we reconstruct shortest paths by going backward through the filled in table? So this is all analogous to Bellman-Ford and Bellman-Ford. We two that on the forward pass, you could maintain the predecessor point it wasn't a big deal, just when you fill in, when you recompute shortest pass in a given round of subproblems. If you compute some new shortest path value, i.e. you don't just inherit that solution from the previous round, you just figure out which vertex was responsible for it and you remember that as your predecessor. And then given the predecessor pointers are correctly computed, you just trace back pointers to reconstruct shortest paths. So here, how do you compute them on the forward direction? Well, remember in the, in the recurrence that we used to fill in the three-dimensional array, A, there's two possibilities, either you just inherit the solution from the previous iteration, that's kind of the boring case. And the interesting case is when you actually use the newly available vertex k in the shortest path from i to j. So whenever you use that second case of the recurrence to reset the value in the three dimensional array A. At that point, you reset the corresponding B(i,j) value to the current value of k. So that is, just add the forward pass of Floyd-Warshall. You always remember the last vertex responsible for changing your shortest path distance between i and j. So now, let's suppose you've coded up this extension of the forward pass of Floyed-Warshall correctly, so that at the end of your triple for loop, you have accurate computations of all of these B(i,j) values. That is, for any origin and desination, you have a little birdy, the two-dimensional array, B, that will just tell you in constant time what is the max labeled vertex internal on a shortest i, j path? Well, maybe you really want to, know your favorite source is 23. Your favorite destination is 17 and you want to reconstruct a shortest path from your oracles, your filled in tables. So you look in to the entry 23, 17 into the B array. You have this little birdy, this filled in table tells you the max labelled vertex on a shortest path between 23 and 17. Maybe it tells you it's the vertex 43. So it promises you that the shortest path comprises 23 on one end, 17 on the other end, a bunch of stuff in the middle, the largest of which is 43. Well, you like, okay cool, let me just, now I know where the shortest has to be. It's the shortest path from 23 to 43 plus a shortest path from 43 to 17, and you just reconstruct those two shortest paths recursively in exactly the same way. This has got to terminate because at the end of the day the shortest path is going to have it most n vertices and you're figuring out one of those vertices everytime you do a recursive call.