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.