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. 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. So, the cycle capital c has non negative costs. That was an arbitrary cycle. So it's true simultaneously of all of the cycles in the input graph. That's exactly what we were trying to prove. So again, the presence of negative cost cycles in an input graph is characterized by the behavior of Bellman Ford in an extra iteration. That's why it's easy to extend the basic algorithm. To check negative cycles without affecting the running time.