0:00

Thus far we've seen how in input graphs without negative cost cycles, the

Bellman-Ford algorithm correctly computes shortest paths from the source vertex S

to all destinations V. But what about input graphs that do have

negative cost cycles? In this short video we'll see how to

extend the Bellman-Ford algorithm leaving its running time essentially unchanged,

so that it can easily check whether or not the input graph has a negative cost

cycle. So the following claim is going to

indicate the appropriate extension of the Bellman-Ford algorithm.

In particular this claim characterizes the presence or absence of a negative

cost cycle in the input graph. In terms of behavior in the Bellman-Ford

algorithm. Okay, well actually, the Bellman-Ford

algorithm if, we ran it for one extra iteration.

So currently, we stop the bellman ford itera algorithm when the outer index I is

equal to N minus one. For the claim we're going to envision

running that outer four loop for one extra iteration, when I equals N running

the same over-currents for all of the destinations V.

[SOUND] So the insertion then is that G the input graph has no negative cycle, if

and only if we don't get any new information from this extra batch of

sub-problems. That is if and only if, A and V is

exactly the same thing as A and -1V for every possible destination V.

Equivalently the input graph does have a negative cost cycle if and only if there

exists some sub-problem. There exists some destination V, where we

see an improvement at V buy running the government Ford out rhythm for this extra

iteration. So we're approved the claim in the next

slide, it's not too hard. But I hope it's immediately clear what

the implications of the claim are. How we check for a negative cost cycle.

So now, given a arbitrary input graph with no promises, it might have a

negative cost cycle, it might not. What do you do?

You run Bellman-Ford but you run it for one more iteration.

You run it for the outer four loop Index I going all the up to N.

And, you check does some sub-problem value change in that final iteration or

not. If not, if all of your A and -1V's are

the same as you A and V's, then, by the claim you know that there's no negative

cost cycle. By our previous work.

We know the Bellmanu2013Ford algorithm is correct.

So, we happily return the A and minus one V'S as the correct shortest path

distances as before. If on the other hand you notice there's

vertex V so, that A and V is different is smaller than A and minus 1V, then you

say, hey. There's a negative cycle by the claim, so

I'm not going to give the shortest path distance for you, that wouldn't make

sense. There is negative path cycle and you

punt. And of course this one extra iteration of

the Bellman-Ford algorithm has a negligible effect on its running time,

it's still Big O of N times N. So I'm lying a little bit in this claim.

There's an edge case I'm not handling properly.

When I wrote down the claim I was thinking about arguably the common case

of input graphs G where there exists a path from S to every other destination V.

That is, input graphs where all of the shortest path distances are finite.

So if that's not the case then the claim as stated is not correct.

one way to see that would be just to generate, to generate instance where the

source vertex S has no outgoing arcs at all and maybe the rest of the vertices

form a negative cost cycle. And that kind of graph.

The left hand side of this claim is false but right hand side of this claim is

satisfied. So to modify it for graphs that may have

infinite distances, I'm just going to modify the left had side to say G has a

negative cost cycle that is reachable from the source for text S.

There are if you actually wanted to detect in the input graph whether there

was a negative cycle at all reachable from s or otherwise there are various

tricks you can do to solve that again using the duman ford algorithm.

So for example given an input graph you can add a dummy sort of fictitious extra

vertex and add arcs from that vertex to everybody else with link zero run them

before on that graph and that will detect a negative graph cycle if one exists.

3:53

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.