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.