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.