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.
