1 00:00:00,000 --> 00:00:03,679 Thus far we've seen how in input graphs without negative cost cycles, the 2 00:00:03,679 --> 00:00:07,813 Bellman-Ford algorithm correctly computes shortest paths from the source vertex S 3 00:00:07,813 --> 00:00:10,988 to all destinations V. But what about input graphs that do have 4 00:00:10,988 --> 00:00:13,912 negative cost cycles? In this short video we'll see how to 5 00:00:13,912 --> 00:00:17,995 extend the Bellman-Ford algorithm leaving its running time essentially unchanged, 6 00:00:17,995 --> 00:00:21,977 so that it can easily check whether or not the input graph has a negative cost 7 00:00:21,977 --> 00:00:25,335 cycle. So the following claim is going to 8 00:00:25,335 --> 00:00:28,817 indicate the appropriate extension of the Bellman-Ford algorithm. 9 00:00:28,817 --> 00:00:32,943 In particular this claim characterizes the presence or absence of a negative 10 00:00:32,943 --> 00:00:36,747 cost cycle in the input graph. In terms of behavior in the Bellman-Ford 11 00:00:36,747 --> 00:00:39,640 algorithm. Okay, well actually, the Bellman-Ford 12 00:00:39,640 --> 00:00:42,158 algorithm if, we ran it for one extra iteration. 13 00:00:42,158 --> 00:00:46,605 So currently, we stop the bellman ford itera algorithm when the outer index I is 14 00:00:46,605 --> 00:00:49,606 equal to N minus one. For the claim we're going to envision 15 00:00:49,606 --> 00:00:53,731 running that outer four loop for one extra iteration, when I equals N running 16 00:00:53,731 --> 00:00:56,571 the same over-currents for all of the destinations V. 17 00:00:56,571 --> 00:01:01,534 [SOUND] So the insertion then is that G the input graph has no negative cycle, if 18 00:01:01,534 --> 00:01:05,634 and only if we don't get any new information from this extra batch of 19 00:01:05,634 --> 00:01:08,386 sub-problems. That is if and only if, A and V is 20 00:01:08,386 --> 00:01:12,368 exactly the same thing as A and -1V for every possible destination V. 21 00:01:12,368 --> 00:01:17,346 Equivalently the input graph does have a negative cost cycle if and only if there 22 00:01:17,346 --> 00:01:21,152 exists some sub-problem. There exists some destination V, where we 23 00:01:21,152 --> 00:01:25,954 see an improvement at V buy running the government Ford out rhythm for this extra 24 00:01:25,954 --> 00:01:29,635 iteration. So we're approved the claim in the next 25 00:01:29,635 --> 00:01:32,935 slide, it's not too hard. But I hope it's immediately clear what 26 00:01:32,935 --> 00:01:36,760 the implications of the claim are. How we check for a negative cost cycle. 27 00:01:36,760 --> 00:01:40,427 So now, given a arbitrary input graph with no promises, it might have a 28 00:01:40,427 --> 00:01:42,942 negative cost cycle, it might not. What do you do? 29 00:01:42,942 --> 00:01:46,242 You run Bellman-Ford but you run it for one more iteration. 30 00:01:46,242 --> 00:01:49,647 You run it for the outer four loop Index I going all the up to N. 31 00:01:49,647 --> 00:01:53,629 And, you check does some sub-problem value change in that final iteration or 32 00:01:53,629 --> 00:01:55,777 not. If not, if all of your A and -1V's are 33 00:01:55,777 --> 00:01:59,863 the same as you A and V's, then, by the claim you know that there's no negative 34 00:01:59,863 --> 00:02:01,540 cost cycle. By our previous work. 35 00:02:01,540 --> 00:02:04,461 We know the Bellmanu2013Ford algorithm is correct. 36 00:02:04,461 --> 00:02:08,784 So, we happily return the A and minus one V'S as the correct shortest path 37 00:02:08,784 --> 00:02:12,465 distances as before. If on the other hand you notice there's 38 00:02:12,465 --> 00:02:17,022 vertex V so, that A and V is different is smaller than A and minus 1V, then you 39 00:02:17,022 --> 00:02:19,569 say, hey. There's a negative cycle by the claim, so 40 00:02:19,569 --> 00:02:23,425 I'm not going to give the shortest path distance for you, that wouldn't make 41 00:02:23,425 --> 00:02:25,606 sense. There is negative path cycle and you 42 00:02:25,606 --> 00:02:29,444 punt. And of course this one extra iteration of 43 00:02:29,444 --> 00:02:33,022 the Bellman-Ford algorithm has a negligible effect on its running time, 44 00:02:33,022 --> 00:02:37,115 it's still Big O of N times N. So I'm lying a little bit in this claim. 45 00:02:37,115 --> 00:02:39,771 There's an edge case I'm not handling properly. 46 00:02:39,771 --> 00:02:43,702 When I wrote down the claim I was thinking about arguably the common case 47 00:02:43,702 --> 00:02:47,952 of input graphs G where there exists a path from S to every other destination V. 48 00:02:47,952 --> 00:02:51,830 That is, input graphs where all of the shortest path distances are finite. 49 00:02:51,830 --> 00:02:55,336 So if that's not the case then the claim as stated is not correct. 50 00:02:55,336 --> 00:02:59,586 one way to see that would be just to generate, to generate instance where the 51 00:02:59,586 --> 00:03:03,783 source vertex S has no outgoing arcs at all and maybe the rest of the vertices 52 00:03:03,783 --> 00:03:06,440 form a negative cost cycle. And that kind of graph. 53 00:03:06,440 --> 00:03:11,601 The left hand side of this claim is false but right hand side of this claim is 54 00:03:11,601 --> 00:03:14,933 satisfied. So to modify it for graphs that may have 55 00:03:14,933 --> 00:03:19,963 infinite distances, I'm just going to modify the left had side to say G has a 56 00:03:19,963 --> 00:03:24,210 negative cost cycle that is reachable from the source for text S. 57 00:03:24,210 --> 00:03:28,517 There are if you actually wanted to detect in the input graph whether there 58 00:03:28,517 --> 00:03:32,824 was a negative cycle at all reachable from s or otherwise there are various 59 00:03:32,824 --> 00:03:36,734 tricks you can do to solve that again using the duman ford algorithm. 60 00:03:36,734 --> 00:03:41,325 So for example given an input graph you can add a dummy sort of fictitious extra 61 00:03:41,325 --> 00:03:45,802 vertex and add arcs from that vertex to everybody else with link zero run them 62 00:03:45,802 --> 00:03:50,280 before on that graph and that will detect a negative graph cycle if one exists. 63 00:03:53,300 --> 00:03:57,965 So now that we know why we want the claim to be true, let's understand why it is 64 00:03:57,965 --> 00:04:00,180 true. Let's go to the proof. 65 00:04:00,180 --> 00:04:02,765 So the claim asserts something that's if, and only if. 66 00:04:02,765 --> 00:04:06,716 On the left-hand side is the property of the input graph having no negative cost 67 00:04:06,716 --> 00:04:08,911 cycle. On the right-hand side is the property 68 00:04:08,911 --> 00:04:12,911 that the Bellman-Ford algorithm does not make any changes if you, run one extra 69 00:04:12,911 --> 00:04:15,106 iteration. So proofs like this have two parts. 70 00:04:15,106 --> 00:04:18,423 Assuming the left, prove the right. Assuming the right, prove the left. 71 00:04:18,423 --> 00:04:22,082 One of these two parts, if you think about it, we already did, when we proved 72 00:04:22,082 --> 00:04:24,180 that the Bellman-Ford algorithm is correct. 73 00:04:24,180 --> 00:04:27,936 Four graphs with no negative cost cycles. That is, if the left-hand side holds. 74 00:04:27,936 --> 00:04:30,570 If the input graph doesn't have a negative cost cycle. 75 00:04:30,570 --> 00:04:34,681 We already argued that you don't have to run the outer four loop beyond I Equals N 76 00:04:34,681 --> 00:04:39,250 minus one that is sufficient to capture the shortest path so in particular take I 77 00:04:39,250 --> 00:04:43,874 as big as you like for example I equals N your not going to see even shorter paths 78 00:04:43,874 --> 00:04:47,050 your going to get exactly the same sub problem solutions. 79 00:04:47,050 --> 00:04:50,310 The content, then, is the reverse direction. 80 00:04:50,310 --> 00:04:56,209 So let's assume that we run Bellman-Ford an extra iteration, and none of the 81 00:04:56,209 --> 00:05:01,635 sub-problem solutions change. Now I warned you there is this edge case 82 00:05:01,635 --> 00:05:05,558 when the input graph doesn't have a path from s to all other verticies and you 83 00:05:05,558 --> 00:05:09,630 have infinite distances I'll leave those details to you so lets just focus on the 84 00:05:09,630 --> 00:05:13,504 case when there is a path from s to everything else and in particular the sub 85 00:05:13,504 --> 00:05:17,656 problem of values are going to be finite. So a little notation. 86 00:05:17,656 --> 00:05:22,787 I'm going to use lowercase D of a vertex V to denote the common value of its 87 00:05:22,787 --> 00:05:28,195 sub-problems in the final two iterations, when I equals N minus one and when I 88 00:05:28,195 --> 00:05:31,751 equals N. So now the plan is we're just going to 89 00:05:31,751 --> 00:05:35,237 stare at the formula that we used to evaluate these sub problems. 90 00:05:35,237 --> 00:05:39,153 It's right there staring at us from the pseudo code for the Bellman Ford 91 00:05:39,153 --> 00:05:41,620 algorithm. From that we will get an inequality 92 00:05:41,620 --> 00:05:45,589 relating these D values to each other. And from that inequality we will be 93 00:05:45,589 --> 00:05:49,933 easily able to deduce that every cycle of the input graph is indeed non negative. 94 00:05:49,933 --> 00:05:52,660 That's the left hand side of the statement. 95 00:05:52,660 --> 00:05:56,788 [SOUND] So what formula did we use to fill in this extra iteration of the 96 00:05:56,788 --> 00:05:59,913 table, the A N Vs? Well we just took the better of, on the 97 00:05:59,913 --> 00:06:04,098 one hand, A N minus one V, the solution from the previous iteration, and then 98 00:06:04,098 --> 00:06:08,673 also the best of the candidates that use c last hop W V and concatenate a path of 99 00:06:08,673 --> 00:06:11,853 the most N minus one edges to W along with that edge W V. 100 00:06:11,853 --> 00:06:17,754 [SOUND] Let's also note that with our new notations these little d values the 101 00:06:17,754 --> 00:06:22,685 common value of a sub problem in the n minus one and f iterations you can write 102 00:06:22,685 --> 00:06:27,677 the left hand side of this formula is d of v and in the case two sub problems we 103 00:06:27,677 --> 00:06:32,477 can write a and minus one w as d of w. Now because the left hand side of this 104 00:06:32,477 --> 00:06:36,513 equation is a minimum over a bunch of candidates on the right hand side if we 105 00:06:36,513 --> 00:06:40,497 instantiate if we zoom in on any one candidate on the right hand side so any 106 00:06:40,497 --> 00:06:44,429 choice of this last hop wv we get something which is at least as big as the 107 00:06:44,429 --> 00:06:49,200 left hand side again the left hand side is the smallest of all of the candidates. 108 00:06:49,200 --> 00:06:56,354 So in particular for a given choice of the last hop w comma v we get that d of v 109 00:06:56,354 --> 00:07:02,080 is at most d of w plus the length of the edge of w to v. 110 00:07:02,080 --> 00:07:08,320 Really all this inequality is saying is that one way to get a path from S to V is 111 00:07:08,320 --> 00:07:13,266 to take a path from S to W in concatenates the final hop W, V, the 112 00:07:13,266 --> 00:07:19,202 shortest path to V can only be better than this one particular candidate that 113 00:07:19,202 --> 00:07:22,953 goes via W. Now, remember what it is we're trying to 114 00:07:22,953 --> 00:07:25,246 prove. We're trying to prove that the input 115 00:07:25,246 --> 00:07:29,086 graph has no negative cost cycles. So, let's just pick our favorite cycle, 116 00:07:29,086 --> 00:07:32,220 capital c and show that it has non negative cost. 117 00:07:32,220 --> 00:07:35,488 This is going to be in a sneaky application of the inequality that we 118 00:07:35,488 --> 00:07:39,488 just wrote down in pink specifically we are going to sum that inequality over all 119 00:07:39,488 --> 00:07:42,464 of the edges in the cycle. its going to be clear if I just 120 00:07:42,464 --> 00:07:45,400 rearranged that pink inequality a little bit. 121 00:07:45,400 --> 00:07:49,240 So, now let's look at the, some of the edge links in the cycle capital so you 122 00:07:49,240 --> 00:07:52,540 remember this is what we want to prove as non-negative. 123 00:07:52,540 --> 00:07:58,026 So, we sum over the edges w coma v in big c and for each edge, we look at its cost, 124 00:07:58,026 --> 00:08:01,548 little c of w v. By the pink inequality, we can lower 125 00:08:01,548 --> 00:08:07,237 bound this by a sum over the edges in the cycle capital C of the difference between 126 00:08:07,237 --> 00:08:11,160 the d values of that edge, the endpoints of the edge. 127 00:08:11,160 --> 00:08:16,787 Notice that for a given arc wv on the cycle the tail of this arc w its d value 128 00:08:16,787 --> 00:08:22,770 appears with a coefficient of plus one and the devalue of the head of this arc v 129 00:08:22,770 --> 00:08:28,690 appears with a coefficient of minus one. But cycles, of course, have the very 130 00:08:28,690 --> 00:08:33,612 special property that every vertex of the cycle appears exactly once as the tail of 131 00:08:33,612 --> 00:08:36,542 some arc and exactly once as the head of some arc. 132 00:08:36,542 --> 00:08:41,054 So each D value of a vertex on a cycle is going to appear once with plus one 133 00:08:41,054 --> 00:08:43,867 coefficient and once with minus one coefficient. 134 00:08:43,867 --> 00:08:47,500 So when we get massive cancellation, we're left with just zero. 135 00:08:48,880 --> 00:08:51,418 So, the cycle capital c has non negative costs. 136 00:08:51,418 --> 00:08:55,281 That was an arbitrary cycle. So it's true simultaneously of all of the 137 00:08:55,281 --> 00:08:58,813 cycles in the input graph. That's exactly what we were trying to 138 00:08:58,813 --> 00:09:01,296 prove. So again, the presence of negative cost 139 00:09:01,296 --> 00:09:05,711 cycles in an input graph is characterized by the behavior of Bellman Ford in an 140 00:09:05,711 --> 00:09:08,857 extra iteration. That's why it's easy to extend the basic 141 00:09:08,857 --> 00:09:11,230 algorithm. To check negative cycles without 142 00:09:11,230 --> 00:09:12,720 affecting the running time.