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.

Â