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.

Â