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.