So with that setup, what are the possible candidates for

what capital P could possibly be?

We're going to have our usual trivial case 1,

which is that if this path P doesn't bother to use up its full edge budget,

that is if it has (i-1) edges or less, well then, naturally,

P better be the shortest s-v path that has at most (i-1) edges.

So the non-trivial case is when the shortest path with the most i

edges from s to v actually uses its full budget, uses all i of its edges.

So now, by analogy, with all of our previous dynamic programming algorithms,

where we think about plucking off the final part of an optimal solution,

here we're going to pluck off the final edge from the path p.

What do we get?

Well, we get a path with one fewer edge.

So that's good, it's going to correspond to some smaller sub-problem,

because it has at most i-1 edges.

On the other hand, notice that if we take a path from s to v and

we pluck off the final edge, we get a path from s to somewhere else.

So we're going to call that somewhere else w.