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.