So now that we know why we want the claim to be true, let's understand why it is

true. Let's go to the proof.

So the claim asserts something that's if, and only if.

On the left-hand side is the property of the input graph having no negative cost

cycle. On the right-hand side is the property

that the Bellman-Ford algorithm does not make any changes if you, run one extra

iteration. So proofs like this have two parts.

Assuming the left, prove the right. Assuming the right, prove the left.

One of these two parts, if you think about it, we already did, when we proved

that the Bellman-Ford algorithm is correct.

Four graphs with no negative cost cycles. That is, if the left-hand side holds.

If the input graph doesn't have a negative cost cycle.

We already argued that you don't have to run the outer four loop beyond I Equals N

minus one that is sufficient to capture the shortest path so in particular take I

as big as you like for example I equals N your not going to see even shorter paths

your going to get exactly the same sub problem solutions.

The content, then, is the reverse direction.

So let's assume that we run Bellman-Ford an extra iteration, and none of the

sub-problem solutions change. Now I warned you there is this edge case

when the input graph doesn't have a path from s to all other verticies and you

have infinite distances I'll leave those details to you so lets just focus on the

case when there is a path from s to everything else and in particular the sub

problem of values are going to be finite. So a little notation.

I'm going to use lowercase D of a vertex V to denote the common value of its

sub-problems in the final two iterations, when I equals N minus one and when I

equals N. So now the plan is we're just going to

stare at the formula that we used to evaluate these sub problems.

It's right there staring at us from the pseudo code for the Bellman Ford

algorithm. From that we will get an inequality

relating these D values to each other. And from that inequality we will be

easily able to deduce that every cycle of the input graph is indeed non negative.

That's the left hand side of the statement.

[SOUND] So what formula did we use to fill in this extra iteration of the

table, the A N Vs? Well we just took the better of, on the

one hand, A N minus one V, the solution from the previous iteration, and then

also the best of the candidates that use c last hop W V and concatenate a path of

the most N minus one edges to W along with that edge W V.

[SOUND] Let's also note that with our new notations these little d values the

common value of a sub problem in the n minus one and f iterations you can write

the left hand side of this formula is d of v and in the case two sub problems we

can write a and minus one w as d of w. Now because the left hand side of this

equation is a minimum over a bunch of candidates on the right hand side if we

instantiate if we zoom in on any one candidate on the right hand side so any

choice of this last hop wv we get something which is at least as big as the

left hand side again the left hand side is the smallest of all of the candidates.

So in particular for a given choice of the last hop w comma v we get that d of v

is at most d of w plus the length of the edge of w to v.

Really all this inequality is saying is that one way to get a path from S to V is

to take a path from S to W in concatenates the final hop W, V, the

shortest path to V can only be better than this one particular candidate that

goes via W. Now, remember what it is we're trying to

prove. We're trying to prove that the input

graph has no negative cost cycles. So, let's just pick our favorite cycle,

capital c and show that it has non negative cost.

This is going to be in a sneaky application of the inequality that we

just wrote down in pink specifically we are going to sum that inequality over all

of the edges in the cycle. its going to be clear if I just

rearranged that pink inequality a little bit.

So, now let's look at the, some of the edge links in the cycle capital so you

remember this is what we want to prove as non-negative.

So, we sum over the edges w coma v in big c and for each edge, we look at its cost,

little c of w v. By the pink inequality, we can lower

bound this by a sum over the edges in the cycle capital C of the difference between

the d values of that edge, the endpoints of the edge.

Notice that for a given arc wv on the cycle the tail of this arc w its d value

appears with a coefficient of plus one and the devalue of the head of this arc v

appears with a coefficient of minus one. But cycles, of course, have the very

special property that every vertex of the cycle appears exactly once as the tail of

some arc and exactly once as the head of some arc.

So each D value of a vertex on a cycle is going to appear once with plus one

coefficient and once with minus one coefficient.

So when we get massive cancellation, we're left with just zero.