0:33

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.

1:27

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.

2:13

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.

3:23

[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?

6:24

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.

7:29

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.

10:30

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.