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. 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. 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. 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. 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. 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.