0:00

Now that we understand the optimal substructure present in shortest paths,

Â we can follow our usual dynamic programming recipe to arrive at the basic

Â version of the Bellman-Ford algorithm. Let's compile our optimal substructure

Â lemma into a recurrence of formula that says how the optimal solution of a given

Â sub problem depends on that of smaller sub problems.

Â I'll use the notation capital L sub I V to denote the optimal solution value of

Â the corresponding subproblem. Subproblems being indexed by two

Â parameters, one V, that's the destination we're interested in, in this subproblem.

Â In the second one is the budget I on the number of edges that are permitted in

Â paths from S to V in this subproblem. So, a few details.

Â First of all, remember that in the last video we proved the optimal substructure

Â limit in general for general graph G, which may indeed have negative cycles.

Â For that reason, we have to allow cycles in shortest paths from S to V.

Â We're not concerned about the cycle being traverse an infinite number of times,

Â because we have this finite budget I and the number of edges that we permit.

Â 1:08

I also need to explain what I mean in the case that there are no paths from S to V

Â within most I edges, and indeed when I is very small, that will in fact be the case

Â for many destinations V, so if there's no way to get from S to V using I hops, we

Â just define LIV to be plus infinity. And as usual, in the recurrence which is

Â going to be defined for every positive integer I and every possible destination

Â V we're just going to state that the optimal solution value for the sub

Â problem is the best of the possible candidates identified in the optimal

Â substructure lemma. That is, capital L sub IV, the optimal

Â solution value for the sub-problem with parameters I and V is the best of all of

Â the possibilities. So let me start with a minimum to take

Â the best of the case one candidate and the case two candidate.

Â The case one candidate is simple enough. One option is always just to inherit the

Â best path we found from s to v that uses only I-1 edges or less.

Â In case two, you'll recall from the quiz at the end of the last video really

Â comprises a number of sub cases, one for each choice of the finally hop.

Â So here we're going to have another minimum ranging over all possible edges

Â WV. For a given choice of that last hop.

Â The shortest path length is going to be the shortest path from s to that choice

Â of w that uses the most I minus one edges.

Â And then of course we also we incur the edge cost of the final hop, w comma v.

Â Correctness, as usual, follows immediately from the optimal substructure

Â lemma. We know these are the only candidates,

Â and by the definition of the recurrence, we pick the best one.

Â Because the optimal substructure lemma has been proven.

Â Whether or not g has a negative cycle, this recurrence is correct for all

Â positive values of I, whether or not g has a negative cycle.

Â So now, let's see how it's useful to assume that the input graph g does not

Â have a negative cycle. So we had a quiz not too long ago, that

Â discussed the use of the no negative cycles hypothesis.

Â In particular, we argued that N-1 edges are always enough to capture a shortest

Â path, between S and any possible destination.

Â Why? Well, suppose there's no negative cycles,

Â picks a destination V, show me a path that has at least N edges.

Â If it has at least N edges, then it visits at least N plus one vertices.

Â There's only N vertices, so the path must visit some vertex twice,

Â and in between two consecutive visits of a given vertex that's a directed cycle.

Â My hypothesis? There are no negative directed cycles,

Â they're all non negative. So if I throw out this directed cycle from this path, I

Â get a new path to the same destination V and it's overall length has only gone

Â down. Discarding cycles only makes paths

Â shorter. That's why there's a shortest path with, with no repeated vertices,

Â that is with at most n minus one edges. So what does this observation have to do

Â with our recurrence? Well it tells us, when you only need to

Â compute the end recurrence, evaluate sub problems for values of I up to n minus

Â one. There is no point in giving a sub problem

Â a budget bigger than n minus one edges if there are no negative cycles.

Â It's not going to be useful. You're guaranteed to have already found

Â the shortest path by the time I has gone as large as n minus one.

Â 4:34

So, to make sure this point is clear, let me just formally write down the

Â subproblems that we're going to solve in the Bellman-Ford algorithm, and which are

Â going to be sufficient to correctly compute shortest paths for input graph g

Â that do not have negative cycles. The subproblems are simply to compute the

Â shortest path links capital L sub of IV. Of course, for all destinations, we're

Â responsible for ultimately computing shortest paths to every destination V,

Â and for all relevant choices of the edge budget I.

Â And so the base case is going to be when I equals zero, and we just said it has to

Â go up as n minus 1, and no further. And this is actually a pleasingly

Â parsimonious collection of sub-problems. It may strike you actually kind of a lot,

Â because there is a quadratic number, or there's N choices for the destination V,

Â and then I is rank taking on N different values.

Â But remember, unlike all the other problems we've been talking about, the

Â output of this problem is linear size. We're suppose to output a number for each

Â destination V. So, we really only have a linear number

Â of sub-problems for each statistic we're responsible for computing,

Â and that's as good as we've had on any of our other programming algorithms.

Â 5:45

So now it's a simple matter to write out the pseudo-code of the justifiably famous

Â Bellman-Ford algorithm Because there are subproblems that are indexed by two

Â parameters, the edge budget I and the decimation V, we are going to have a

Â two-dimension array A. Remember that we're measuring sub-problem

Â size via the edge budget I. That's sort of the great idea in the

Â Bellman-Ford algorithm, to introduce this edge budget to control sub-problem size.

Â So the base case is when I equals zero, and then we're talking about getting from

Â S to some vertex V, using zero edges. Okay, well if V happens to equal S, then

Â you can do it with the empty path, and the length of the empty path is zero.

Â But if V is any vertex other than S, then, of course, you can't get from S to

Â V using zero edges, and remember in that case,

Â we define the optimum value solution to be plus infinity.

Â 6:36

So now we move onto are customary double four-loop, one four-loop for each of the

Â indices that a nexus R array A. But actually, what's interesting is

Â unlike most of the dynamic programming algorithms we're discussing, here the

Â order of the four-loop matters. You can not pick arbitrarly.

Â You really need to make sure that you have all the smaller subproblems solved

Â by the time you need them. That means the outer four-loop should be

Â indexed by the subproblem size I. So, as we discussed, we're not going to

Â bother letting I range above n minus one. That's going to be sufficient for in the

Â case where there are no negative cycles, and for each choice of I, we solve all of

Â the corresponding sub problems, all destinations v.

Â 7:16

For each choice of I and V, of course, we just write down in code the formula that

Â we stated in the recurrence. So as I'm sure you recall, case one

Â furnishes one possible candidate. It's always an option to just inheret, the

Â shortest path from S to V that you computed using only, I-1 edges.

Â Alternatively from case two, there's also one candidate furnished for each twist of

Â the final hop, so for each edge, that ends at V, for each choice W comma V,

Â there's an option of taking a shortest path from S to W, that uses only, I minus

Â 1 edges, and tacking on that final edge, WV.

Â And as we've discussed, if it just so happens that the input graph G has no

Â negative cycles, then this algorithm will indeed terminate with a correct shortest

Â path from S to all of the destinations. Those answers will be lying in wait for

Â you, in the biggest subproblems, the A N minus 1 V's.

Â So that's correctness as usual. It follows primarily from the optimal

Â substructure lemma, but in this case also the hypothesis of no negative cycles

Â guarantees that taking I equal N minus one is large enough to actually capture

Â the final answers. So we'll talk about the running time of

Â the Bellman-Ford algorithm in a sec, but first let's just go through a quick

Â example to make sure all of this makes sense.

Â