So let me start now setting up the optimal substructure limit.
In contrast to the Bellman-Ford case, I'm only going to prove the optimal
substructure limit of four input graphs that have no negative cycle.
We'll address the case of negative cycles after we're done with the algorithm.
Suppose for now there isn't one. So what then are the subproblems going to
be? Well it's going to be quite analogous to
Bellman-Ford. In Bellman-Ford we were solving a single
source shortest path problem so we needed to compute something for each
destination. So that gave us a linear number of
sub-problems and then for a given destination we had this parameter I
controlling the edge budget. So that was another linear factor, so we
had a quadratic number of subproblems. Here it's going to be the same except we
also have to range over our own origin. So we're going to get a cubic number of
subproblems, specifically a choice for the origin, N choices, a choice for the
destination, that's N more choices plus. Which prefix of vertices we're allowed to
use. So that's still another N choices.
So cubic total. So now we focus on an optimal solution to
this sub problem. By which I mean amongst all paths which
begin at the vertex I, end at the vertex J, and strictly in between I and J, as
internal nodes contain only vertices from one through K.
Amongst all those paths look at the one with the shortest length.
And because we're looking at the case of no negative cycles, we can assume that
this path has no cycles. It's a cycle free path.
So rather than state the conclusion of the optimal substructure lemma right now,
let me just make sure you understand what one of these sub-problems is.
So, lets suppose that the origin is the vertex that we've, aren't labelled
arbitrarily seventeen, the destination J is the vertex we've labelled ten, and
let's suppose K at the moment is only five.
Consider the following graph. Imagine this is a little piece of some
much bigger graph. Now I hope it's clear what the shortest
path is between seventeen and ten. It's the bottom two hop path, that path
has total length minus twenty. On the other hand, for the sub problem
we're dealing with, K equals five. So what that means is we have this extra
constraint on which vertices can we can use in the middle of our paths.
Now to be clear, this constraint K at most five that can't apply to origin of
the destination. Right?
I is 17, J is 10, both of those are bigger than five, but we don't care.
Obviously, any path from I to J, has to include both the vertices I and J.
So the constraint only applies to vertices in the middle of the path.
But, this bottom two hot path, unfortunately makes use of the node
seven. So that path does not obey the
constraint, it is not at most five, so that path is disallowed.
Can not use it. Therefore, the shortest path from
seventeen to ten, that makes use of only the first five The five labeled vertices
as intermediate ones would be the top three hot path, which has the bigger
length of three. Oay, so I hope it's clear what a c-
sub-problem corresponds to. It corresponds to a choice of I, the
origin. That's again just some vertex labeled
something from one to N. Similarly there's a choice of the
destination, some other vertex J which is labeled something from one to N.
And then there's a choice of the bound K. Which governs which vertices you're
permitted to use internal to your path. So again the constraint doesn't apply to
the end points, just the vertices in between the end points.
And in the subproblem the choice of K says you can only use vertices one
through K, internal to your paths. So hopefully that makes sense, let's move
on to the full statement of the optimal substructure lema.
