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.