1 00:00:01,830 --> 00:00:04,180 - [Instructor] So in an earlier video, 2 00:00:04,180 --> 00:00:06,563 we saw Dijkstra's algorithm. 3 00:00:07,550 --> 00:00:12,550 We saw how we can take a graph, weighted edges 4 00:00:13,200 --> 00:00:16,420 and find the shortest path 5 00:00:16,420 --> 00:00:21,230 from some node to all the other nodes in the graph. 6 00:00:21,230 --> 00:00:22,360 And that's great. 7 00:00:22,360 --> 00:00:24,720 And that worked as long as we didn't have 8 00:00:24,720 --> 00:00:26,393 any negative edge weights. 9 00:00:27,720 --> 00:00:30,520 When we talk about the shortest path, 10 00:00:30,520 --> 00:00:34,930 we really should be talking about the lowest cost path. 11 00:00:34,930 --> 00:00:38,930 And it turns out that there are a lot of applications 12 00:00:38,930 --> 00:00:41,410 where we may have positive and negative weights 13 00:00:41,410 --> 00:00:45,883 that don't necessarily refer to distances. 14 00:00:46,730 --> 00:00:48,790 We talk about the shortest path in a graph, 15 00:00:48,790 --> 00:00:51,800 but the actual real world problem that we're modeling 16 00:00:51,800 --> 00:00:56,193 might be measured in dollars or in calories. 17 00:00:57,090 --> 00:00:59,640 We have a graph here on the left 18 00:00:59,640 --> 00:01:00,940 that has some negative weights. 19 00:01:00,940 --> 00:01:03,400 We have negative three, negative two, 20 00:01:03,400 --> 00:01:06,190 and we've learned that Dijkstra's algorithm doesn't work. 21 00:01:06,190 --> 00:01:08,040 It gets grumpy, and it doesn't work 22 00:01:08,040 --> 00:01:09,473 if we have negative weights. 23 00:01:10,720 --> 00:01:13,950 But as I'm hinting, there are many applications 24 00:01:13,950 --> 00:01:16,103 where negative edge weights are useful. 25 00:01:17,160 --> 00:01:19,760 I'll give you a couple of common examples. 26 00:01:19,760 --> 00:01:22,610 One example is currency arbitrage 27 00:01:22,610 --> 00:01:27,610 where we have different exchange rates between currencies 28 00:01:27,850 --> 00:01:32,850 and you can represent these costs of changing currencies 29 00:01:34,130 --> 00:01:36,650 with a graph and you can identify 30 00:01:36,650 --> 00:01:38,870 what are called arbitrage opportunities 31 00:01:38,870 --> 00:01:43,870 by finding lowest cost paths that optimize your profit. 32 00:01:45,330 --> 00:01:47,970 Another example is a chemical reaction 33 00:01:47,970 --> 00:01:51,820 or a chain of chemical reactions. 34 00:01:51,820 --> 00:01:56,020 As you may know, some chemical reactions consume energy 35 00:01:56,020 --> 00:01:59,650 and some chemical reactions give off energy. 36 00:01:59,650 --> 00:02:04,020 And so we might be interested in finding the series 37 00:02:04,020 --> 00:02:07,910 of chemical reactions that yields the lowest cost 38 00:02:07,910 --> 00:02:11,530 or that releases the highest amount of energy. 39 00:02:11,530 --> 00:02:15,050 And so we can model our chemical reactions 40 00:02:15,050 --> 00:02:17,860 where we have positive and negative weights 41 00:02:17,860 --> 00:02:20,630 depending on whether the chemical reaction 42 00:02:20,630 --> 00:02:23,510 consumes energy or releases energy. 43 00:02:23,510 --> 00:02:25,390 So those are two common examples. 44 00:02:25,390 --> 00:02:27,260 I'm gonna give you another. 45 00:02:27,260 --> 00:02:30,810 So in keeping with our earlier discussions 46 00:02:30,810 --> 00:02:35,810 of roots and cities, what's shown here aren't distances, 47 00:02:36,560 --> 00:02:38,100 but are costs. 48 00:02:38,100 --> 00:02:41,280 So let's say we have a truck, we've got a truck. 49 00:02:41,280 --> 00:02:42,113 Here's our truck. 50 00:02:42,113 --> 00:02:43,970 Our truck is in Albuquerque, New Mexico 51 00:02:43,970 --> 00:02:46,810 and we want to get home to Fresno, California 52 00:02:48,080 --> 00:02:51,690 with as much money in our pocket as possible. 53 00:02:51,690 --> 00:02:55,610 So the cost of driving the truck is about 42 cents a mile. 54 00:02:55,610 --> 00:02:58,520 We get about seven miles to the gallon. 55 00:02:58,520 --> 00:03:01,820 We got diesels about three bucks a gallon 56 00:03:01,820 --> 00:03:04,890 so call it 42 cents. 57 00:03:04,890 --> 00:03:06,300 But at certain points, 58 00:03:06,300 --> 00:03:08,240 we can pick up goods and deliver them. 59 00:03:08,240 --> 00:03:10,190 I mean, that's the point of having a truck. 60 00:03:10,190 --> 00:03:12,500 So here from Flagstaff to Phoenix, 61 00:03:12,500 --> 00:03:14,460 we can pick up something in Flagstaff 62 00:03:14,460 --> 00:03:19,460 and deliver it to Phoenix and we turn a profit, 70 bucks. 63 00:03:19,900 --> 00:03:22,570 So we represent that as a negative number. 64 00:03:22,570 --> 00:03:24,300 Here, we just have a cost. 65 00:03:24,300 --> 00:03:26,630 This is the cost of our fuel 66 00:03:26,630 --> 00:03:28,940 driving from Albuquerque to Flagstaff. 67 00:03:28,940 --> 00:03:30,410 There's nothing that we can carry 68 00:03:30,410 --> 00:03:33,593 from Albuquerque to Flagstaff to offset that cost. 69 00:03:34,680 --> 00:03:37,690 In some cases, the cost is offset partly, 70 00:03:37,690 --> 00:03:40,060 but in some cases we actually turn a profit. 71 00:03:40,060 --> 00:03:42,550 Again, here's another path with a profit 72 00:03:42,550 --> 00:03:45,940 where we take some say farm goods from Bakersfield 73 00:03:45,940 --> 00:03:47,870 to Los Angeles. 74 00:03:47,870 --> 00:03:51,200 And so we've got all these cities, we've got all these costs 75 00:03:51,200 --> 00:03:53,960 and we want to find the lowest cost path 76 00:03:53,960 --> 00:03:56,120 from Albuquerque to Fresno. 77 00:03:56,120 --> 00:03:59,640 Does that go through Flagstaff and Bakersfield 78 00:03:59,640 --> 00:04:03,410 or does it go through Las Cruces and Tucson? 79 00:04:03,410 --> 00:04:07,990 It looks like we have a high profit trip here 80 00:04:07,990 --> 00:04:10,370 from Tijuana to San Diego, 81 00:04:10,370 --> 00:04:12,580 but it's not immediately evident 82 00:04:12,580 --> 00:04:14,950 what the lowest cost path is. 83 00:04:14,950 --> 00:04:16,530 So what do we do? 84 00:04:16,530 --> 00:04:19,390 We've already seen that Dijkstra's algorithm won't work. 85 00:04:19,390 --> 00:04:20,800 So what can be done? 86 00:04:20,800 --> 00:04:22,853 We use the Bellman-Ford algorithm. 87 00:04:26,390 --> 00:04:30,070 Now we saw earlier that there was the catch, 88 00:04:30,070 --> 00:04:31,440 there's always a catch. 89 00:04:31,440 --> 00:04:34,060 So Dijkstra's algorithm is great. 90 00:04:34,060 --> 00:04:38,393 It has this relatively low worse case complexity, 91 00:04:39,420 --> 00:04:42,260 but we can't work with edge weight that are negative. 92 00:04:42,260 --> 00:04:44,743 If we have a negative edge weight, we're no good. 93 00:04:45,860 --> 00:04:49,340 So we need another solution and we have Bellman-Ford. 94 00:04:49,340 --> 00:04:52,620 Bellman-Ford is a more costly algorithm to run 95 00:04:52,620 --> 00:04:54,680 instead of big O of the cardinality V 96 00:04:54,680 --> 00:04:56,880 plus the cardinality V times the log 97 00:04:56,880 --> 00:04:58,730 of the cardinality of V. 98 00:04:58,730 --> 00:05:01,660 We have a big O of the cardinality V 99 00:05:01,660 --> 00:05:03,600 times the cardinality of E 100 00:05:03,600 --> 00:05:06,500 and we'll see that we have a nested loop in there. 101 00:05:06,500 --> 00:05:08,270 So it's more expensive. 102 00:05:08,270 --> 00:05:11,770 So if we know we have all positive 103 00:05:11,770 --> 00:05:14,160 or I should say all non-negative edge weights, 104 00:05:14,160 --> 00:05:15,570 we should use Dijkstra, 105 00:05:15,570 --> 00:05:17,170 but if we have negative edge weights, 106 00:05:17,170 --> 00:05:19,440 we should use Bellman-Ford, 107 00:05:19,440 --> 00:05:21,610 but there's a restriction for Bellman-Ford too 108 00:05:21,610 --> 00:05:25,550 and that is that there must be no negative cycles. 109 00:05:25,550 --> 00:05:27,800 So that's another restriction here. 110 00:05:27,800 --> 00:05:30,533 So we have to think about what is a negative cycle. 111 00:05:31,590 --> 00:05:35,530 And then once we figure out what a negative cycle is, 112 00:05:35,530 --> 00:05:38,720 I'll walk you through an example of Bellman-Ford. 113 00:05:38,720 --> 00:05:42,380 Here, we've got this directed cyclical graph, 114 00:05:42,380 --> 00:05:45,480 and you can see we have a cycle here. 115 00:05:45,480 --> 00:05:47,710 We have a cycle here. 116 00:05:47,710 --> 00:05:49,790 We have a cycle here. 117 00:05:49,790 --> 00:05:52,140 Now, what is a negative cycle? 118 00:05:52,140 --> 00:05:55,030 Well, this is a counter example. 119 00:05:55,030 --> 00:05:56,520 This is not a negative cycle. 120 00:05:56,520 --> 00:06:00,730 We have edge weights of one plus three minus two 121 00:06:00,730 --> 00:06:05,730 gives us a sum of the edge weights is two 122 00:06:05,930 --> 00:06:09,070 and that's not negative so that's not a negative cycle. 123 00:06:09,070 --> 00:06:10,420 Let's look at this one over here. 124 00:06:10,420 --> 00:06:15,130 We've got one plus two minus three is zero plus seven 125 00:06:15,130 --> 00:06:18,510 so the sum of the edge weights here is seven 126 00:06:18,510 --> 00:06:22,090 and that also is not a negative cycle. 127 00:06:22,090 --> 00:06:24,140 But here we do have a negative cycle. 128 00:06:24,140 --> 00:06:28,910 We have edge weights of three plus two is five minus seven. 129 00:06:28,910 --> 00:06:30,373 This is negative two. 130 00:06:32,180 --> 00:06:34,550 Now, why is this a problem? 131 00:06:34,550 --> 00:06:37,830 Well, if I want to get from one place to another 132 00:06:37,830 --> 00:06:42,830 with the lowest cost, say I wanted to get from A to H, 133 00:06:44,810 --> 00:06:48,250 I could continually reduce my cost 134 00:06:48,250 --> 00:06:49,993 by traveling in this loop. 135 00:06:50,940 --> 00:06:52,700 Every time I go through this loop, 136 00:06:52,700 --> 00:06:55,160 I'm gonna reduce my cost by two. 137 00:06:55,160 --> 00:06:58,580 Negative two, negative four, negative six, negative eight 138 00:06:58,580 --> 00:06:59,440 so I'm gonna start here. 139 00:06:59,440 --> 00:07:00,640 I've got six. 140 00:07:00,640 --> 00:07:04,320 I go around once, I got four, I go around once, I got two, 141 00:07:04,320 --> 00:07:07,630 I go around once, I got zero, I got negative 142 00:07:07,630 --> 00:07:09,800 and there's no end to it. 143 00:07:09,800 --> 00:07:14,800 So this is not a way to find the lowest cost path, 144 00:07:16,010 --> 00:07:19,640 it's gonna lead us to infinite regress. 145 00:07:19,640 --> 00:07:22,340 So that's why we can't have negative cycles 146 00:07:22,340 --> 00:07:26,040 in a graph and use Bellman-Ford. 147 00:07:26,040 --> 00:07:29,440 So what does the Bellman-Ford algorithm look like? 148 00:07:29,440 --> 00:07:32,443 Well, it looks an awful lot like Dijkstra. 149 00:07:34,140 --> 00:07:37,750 Some of the code here is absolutely identical. 150 00:07:37,750 --> 00:07:40,590 So we have this function, Bellman-Ford, just like Dijkstra, 151 00:07:40,590 --> 00:07:44,100 it takes in a graph and a starting node S. 152 00:07:44,100 --> 00:07:46,920 And then the initialization, this part of the code here 153 00:07:46,920 --> 00:07:48,530 is absolutely identical. 154 00:07:48,530 --> 00:07:52,380 For each node in the graph, we set the arrived from 155 00:07:52,380 --> 00:07:55,800 for that node to be null at the starting point. 156 00:07:55,800 --> 00:07:57,620 If the node is the starting node, 157 00:07:57,620 --> 00:07:59,330 we set the distance to zero. 158 00:07:59,330 --> 00:08:01,400 Otherwise, we set it to infinite. 159 00:08:01,400 --> 00:08:03,283 Again, identical to Dijkstra. 160 00:08:06,250 --> 00:08:09,090 Now here we have a little difference, 161 00:08:09,090 --> 00:08:10,830 but before I explain the difference, 162 00:08:10,830 --> 00:08:12,320 I'm gonna draw your attention 163 00:08:12,320 --> 00:08:15,633 to these four lines of code or pseudocode I should say. 164 00:08:16,692 --> 00:08:20,420 And these again are absolutely identical to Dijkstra. 165 00:08:20,420 --> 00:08:22,450 We calculate the distance 166 00:08:22,450 --> 00:08:24,470 which is the distance we've already found 167 00:08:24,470 --> 00:08:28,110 plus the weight of the edge to the new destination. 168 00:08:28,110 --> 00:08:31,560 And if the distance is less than that 169 00:08:31,560 --> 00:08:34,700 of the current value for the destination, 170 00:08:34,700 --> 00:08:36,860 then we know we found a shorter distance 171 00:08:36,860 --> 00:08:39,080 and we do this update where we update the distance 172 00:08:39,080 --> 00:08:40,450 and we update the arrived from. 173 00:08:40,450 --> 00:08:43,653 These four lines of code are identical to Dijkstra. 174 00:08:44,590 --> 00:08:45,920 So what's different? 175 00:08:45,920 --> 00:08:49,870 What's different is that rather than a while loop, 176 00:08:49,870 --> 00:08:52,920 we have to repeat a fixed number of times 177 00:08:52,920 --> 00:08:56,560 or we do have some early termination conditions. 178 00:08:56,560 --> 00:08:57,960 So in the worst case, 179 00:08:57,960 --> 00:09:02,020 we have to repeat the cardinality of V minus one time. 180 00:09:02,020 --> 00:09:04,970 So if you have a graph on six nodes, 181 00:09:04,970 --> 00:09:07,710 we have to repeat this outer loop five times. 182 00:09:07,710 --> 00:09:10,890 If we have a graph of 100 nodes, 183 00:09:10,890 --> 00:09:13,853 we have to repeat this loop 99 times. 184 00:09:15,010 --> 00:09:17,390 And then there's an inner loop 185 00:09:17,390 --> 00:09:20,840 and we have to iterate through all the edges 186 00:09:20,840 --> 00:09:24,310 in the graph for each iteration of the outer loop. 187 00:09:24,310 --> 00:09:27,350 So this is cardinality of V. 188 00:09:27,350 --> 00:09:28,930 This is cardinality of E 189 00:09:28,930 --> 00:09:31,670 and that's where we get the complexity 190 00:09:31,670 --> 00:09:34,940 big O of cardinality of V times the cardinality V 191 00:09:34,940 --> 00:09:36,630 because we have this invested loop, 192 00:09:36,630 --> 00:09:39,573 outer loop is V, inner loop is E. 193 00:09:42,100 --> 00:09:45,240 We also have this check here at the end, 194 00:09:45,240 --> 00:09:48,570 the very end we've executed the algorithm. 195 00:09:48,570 --> 00:09:50,040 We do this check to see 196 00:09:50,040 --> 00:09:52,650 if there are negative cycles in the graph 197 00:09:52,650 --> 00:09:55,070 and we have to go through all of this stuff first 198 00:09:55,070 --> 00:09:56,970 before we can do our check. 199 00:09:56,970 --> 00:10:01,353 For each edge in the graph going from U to V, 200 00:10:02,370 --> 00:10:06,100 we check to see if the distance to V is greater 201 00:10:06,100 --> 00:10:09,190 than the distance to U plus the weight of that edge. 202 00:10:09,190 --> 00:10:11,670 And if it is, we know we found a negative cycle 203 00:10:11,670 --> 00:10:12,890 and I'll give a demonstration 204 00:10:12,890 --> 00:10:16,100 of why that works a little later, 205 00:10:16,100 --> 00:10:19,423 but now let's go through an example of Bellman-Ford. 206 00:10:20,960 --> 00:10:25,960 So here we have this directed cyclic graph. 207 00:10:27,803 --> 00:10:28,963 Do we have cycles here? 208 00:10:31,430 --> 00:10:32,720 Yeah, we do. 209 00:10:32,720 --> 00:10:35,510 So this is a directed cyclical graph, 210 00:10:35,510 --> 00:10:38,340 but it has no negative weight cycles 211 00:10:38,340 --> 00:10:43,340 so we have this cycle here from B to F to D to B again, 212 00:10:44,020 --> 00:10:46,470 but what's the sum here is one. 213 00:10:46,470 --> 00:10:51,060 So this is negative five, but the cycle weight is one. 214 00:10:51,060 --> 00:10:52,060 So we're good there. 215 00:10:53,170 --> 00:10:55,400 We also have this cycle here, two, two, five, 216 00:10:55,400 --> 00:10:56,420 but those are all positive 217 00:10:56,420 --> 00:10:58,403 so that presents no problem for us. 218 00:11:00,640 --> 00:11:03,183 And I've initialized this graph, 219 00:11:04,030 --> 00:11:06,700 the starting node here as weight zero, 220 00:11:06,700 --> 00:11:09,200 all the others have infinity, 221 00:11:09,200 --> 00:11:11,770 just like we would do with Dijkstra 222 00:11:11,770 --> 00:11:15,070 and noticed that we have six nodes 223 00:11:15,070 --> 00:11:19,303 so we would have to execute in the worst case five times. 224 00:11:20,360 --> 00:11:22,830 And over here, this is just a list 225 00:11:22,830 --> 00:11:25,840 of all of the edges in the graph. 226 00:11:25,840 --> 00:11:27,730 So remember at each iteration, 227 00:11:27,730 --> 00:11:29,160 we're gonna have to check this edge 228 00:11:29,160 --> 00:11:30,240 and then this edge and then this edge 229 00:11:30,240 --> 00:11:32,730 and then this edge and then this edge. 230 00:11:32,730 --> 00:11:34,920 So I've got this over here just so we can keep track 231 00:11:34,920 --> 00:11:38,163 of the edges that we've checked so far, just visually. 232 00:11:39,350 --> 00:11:43,380 So on our first iteration, we first check edge AB 233 00:11:43,380 --> 00:11:46,370 and we find a route from A to B, 234 00:11:46,370 --> 00:11:49,087 path from A to B of weight seven. 235 00:11:49,087 --> 00:11:52,960 And so we update the value for B to seven 236 00:11:52,960 --> 00:11:55,030 and indicate that we got there from A, 237 00:11:55,030 --> 00:11:57,130 then we check AF. 238 00:11:57,130 --> 00:11:59,080 What happens with AF? 239 00:11:59,080 --> 00:12:02,127 We've discovered a path F of weight six 240 00:12:02,127 --> 00:12:04,440 and we got there from A. 241 00:12:04,440 --> 00:12:06,760 Now we check BF. 242 00:12:06,760 --> 00:12:11,760 From B to F, we have a weight of seven plus four is 11. 243 00:12:11,780 --> 00:12:15,173 11 is not less than six so we don't update here. 244 00:12:16,900 --> 00:12:18,330 Now we do from B to C 245 00:12:18,330 --> 00:12:22,710 and we've discovered a new shortest path of weight 13 246 00:12:22,710 --> 00:12:25,883 so we make a note of that here, that we arrived from B. 247 00:12:28,850 --> 00:12:33,850 Now we check from D to B, but D to B, D is infinite 248 00:12:33,850 --> 00:12:38,060 and so this is gonna give us infinity minus five, 249 00:12:38,060 --> 00:12:40,730 which is certainly greater than seven 250 00:12:40,730 --> 00:12:42,550 and so we don't do an update. 251 00:12:42,550 --> 00:12:44,870 And then we do D to C, same thing, 252 00:12:44,870 --> 00:12:47,693 infinity minus three, no update. 253 00:12:48,740 --> 00:12:53,740 Infinity plus two is not less than infinity 254 00:12:53,770 --> 00:12:56,320 so we don't do an update there. 255 00:12:56,320 --> 00:13:01,320 And now we check from F to D and we find a path to D 256 00:13:02,980 --> 00:13:07,050 that goes from A to F to D and it has weight eight 257 00:13:07,050 --> 00:13:10,100 and so we make a note that we arrived at D from F. 258 00:13:10,100 --> 00:13:13,520 So there's a new shortest path that we've discovered. 259 00:13:13,520 --> 00:13:18,520 Then we check H to C and we have the same infinity case 260 00:13:18,780 --> 00:13:20,340 so there's no update. 261 00:13:20,340 --> 00:13:23,330 And H to F again, no update. 262 00:13:23,330 --> 00:13:25,803 So that concludes our first iteration. 263 00:13:28,170 --> 00:13:30,230 Now we do our second iteration. 264 00:13:30,230 --> 00:13:32,570 From A to B, there's no change. 265 00:13:32,570 --> 00:13:36,360 From A to F, no change. 266 00:13:36,360 --> 00:13:38,140 From A to B... 267 00:13:38,140 --> 00:13:41,450 I'm sorry, from B to F, that's this one here. 268 00:13:41,450 --> 00:13:45,990 No change, because again, 11 is still greater than six. 269 00:13:45,990 --> 00:13:48,393 We checked it last time, still no change. 270 00:13:49,400 --> 00:13:52,063 From B to C, no change. 271 00:13:52,910 --> 00:13:57,150 From D to B, now we have a change. 272 00:13:57,150 --> 00:14:00,330 We had a weight of seven. 273 00:14:00,330 --> 00:14:03,440 Now we have a weight of three, why? 274 00:14:03,440 --> 00:14:06,300 Because now we found this new shortest path 275 00:14:06,300 --> 00:14:11,300 that goes through D so six plus two minus five is three 276 00:14:13,250 --> 00:14:17,773 and so we arrived at B with this new shortest path from D. 277 00:14:18,840 --> 00:14:22,143 Now we check from D to C and we get an update there. 278 00:14:23,300 --> 00:14:25,670 The old was 13, now it's five 279 00:14:25,670 --> 00:14:27,490 because now we have this shortest path, 280 00:14:27,490 --> 00:14:30,450 six plus two minus three is five 281 00:14:30,450 --> 00:14:34,010 and that's our new shortest path to C from D. 282 00:14:34,010 --> 00:14:39,010 Now we check D to H and we get a new shortest path here. 283 00:14:39,750 --> 00:14:44,070 We had infinity, now it's 10 because D is eight 284 00:14:44,070 --> 00:14:46,423 plus two is 10. 285 00:14:49,040 --> 00:14:54,040 Now from F to D, F to D, we've got no change here. 286 00:14:57,200 --> 00:15:00,043 And we check H to see. 287 00:15:00,960 --> 00:15:05,300 10 plus five is 15 is greater than six so no update. 288 00:15:05,300 --> 00:15:07,510 And H to F... 289 00:15:07,510 --> 00:15:10,680 I'm sorry, I should have checked this one here. 290 00:15:10,680 --> 00:15:15,680 That was 10 plus one is greater than five so no update 291 00:15:15,840 --> 00:15:20,640 and now 10 plus five is 15 is greater than six so no update. 292 00:15:20,640 --> 00:15:23,440 And that concludes our second iteration. 293 00:15:23,440 --> 00:15:25,400 Now I've contrived this example 294 00:15:25,400 --> 00:15:29,110 so that we have no updates in the third iteration. 295 00:15:29,110 --> 00:15:33,500 So you'll see what early termination looks like. 296 00:15:33,500 --> 00:15:36,300 And so we check AB, no change. 297 00:15:36,300 --> 00:15:37,753 AF, no change. 298 00:15:37,753 --> 00:15:42,130 BF, no change, BC, no change. 299 00:15:42,130 --> 00:15:45,140 D to B, no change. 300 00:15:45,140 --> 00:15:49,670 D to C, no change and so on through the rest of the graph. 301 00:15:49,670 --> 00:15:52,870 And so we've made an iteration without any updates 302 00:15:52,870 --> 00:15:56,330 and therefore we know that any subsequent iterations 303 00:15:56,330 --> 00:15:59,330 will also have no updates so we can terminate early. 304 00:15:59,330 --> 00:16:03,360 So we're done with this part of the algorithm 305 00:16:03,360 --> 00:16:06,330 and now we check for negative cycles. 306 00:16:06,330 --> 00:16:07,660 And if you'll recall, 307 00:16:07,660 --> 00:16:11,990 the way we checked for negative cycles is we check to see 308 00:16:11,990 --> 00:16:14,450 is the distance to B here 309 00:16:14,450 --> 00:16:18,307 greater than the distance from this node 310 00:16:20,010 --> 00:16:21,760 plus the edge weight. 311 00:16:21,760 --> 00:16:25,163 And no, three is not greater than zero plus seven. 312 00:16:26,400 --> 00:16:30,590 We check this one, six is not greater than zero plus six 313 00:16:30,590 --> 00:16:31,743 so we're good there. 314 00:16:33,210 --> 00:16:37,500 B to F, we have three plus four is seven. 315 00:16:37,500 --> 00:16:41,020 Six is not greater than seven, so we're good there. 316 00:16:41,020 --> 00:16:46,020 B to C, five is not greater than three plus six 317 00:16:46,370 --> 00:16:47,653 so we're good there. 318 00:16:49,210 --> 00:16:54,020 D to B is eight minus five. 319 00:16:54,020 --> 00:16:56,740 Three is not greater than eight minus five 320 00:16:56,740 --> 00:16:57,850 so we're good there 321 00:16:57,850 --> 00:17:00,510 and so on throughout the rest of the graph. 322 00:17:00,510 --> 00:17:03,980 So all of these edges pass that test. 323 00:17:03,980 --> 00:17:07,970 And so we have no negative cycles and we're done. 324 00:17:07,970 --> 00:17:10,190 And as before with Dijkstra, 325 00:17:10,190 --> 00:17:14,150 we can reconstruct any shortest path 326 00:17:14,150 --> 00:17:15,480 by following these pointers. 327 00:17:15,480 --> 00:17:18,403 So for example, the path from B, 328 00:17:19,240 --> 00:17:20,900 we go backwards to D. 329 00:17:20,900 --> 00:17:22,770 From D, we go backwards to F. 330 00:17:22,770 --> 00:17:25,420 From F, we go backwards to A, and so we know 331 00:17:25,420 --> 00:17:30,230 that this shortest path to B, which is of weight three 332 00:17:30,230 --> 00:17:34,820 is this path from A to F to D to B, and we can do this 333 00:17:34,820 --> 00:17:37,820 for any node in the graph, 334 00:17:37,820 --> 00:17:39,520 find its way back to A. 335 00:17:39,520 --> 00:17:41,940 So that's again just like Dijkstra's. 336 00:17:44,030 --> 00:17:47,943 So why do we need up to V minus one iterations? 337 00:17:49,150 --> 00:17:54,150 Well, if we have the cardinality of V nodes, 338 00:17:54,410 --> 00:17:57,140 then the shortest path can have no more 339 00:17:57,140 --> 00:18:00,680 than the cardinality of V minus one edges. 340 00:18:00,680 --> 00:18:03,490 And when we iterate at the case iteration, 341 00:18:03,490 --> 00:18:07,563 we know we've covered all the shortest paths up to length K, 342 00:18:08,450 --> 00:18:10,950 now we need to consider all the shortest paths 343 00:18:10,950 --> 00:18:15,320 so we need K to equal the cardinality of V minus one. 344 00:18:15,320 --> 00:18:20,320 So at each iteration, we may add more and more length 345 00:18:20,790 --> 00:18:22,230 to some of these paths 346 00:18:22,230 --> 00:18:27,230 and therefore we need to iterate up to the maximum possible. 347 00:18:27,350 --> 00:18:32,300 So that's why we need V minus one iterations. 348 00:18:32,300 --> 00:18:34,943 And how does the check for negative cycles work? 349 00:18:35,970 --> 00:18:38,650 Well, as you recall from the pseudocode, 350 00:18:38,650 --> 00:18:40,560 once we've processed the graph 351 00:18:40,560 --> 00:18:44,950 with our cardinality of V minus one iterations 352 00:18:44,950 --> 00:18:47,950 or sooner if we have early stopping criteria, 353 00:18:47,950 --> 00:18:48,860 we check the weights. 354 00:18:48,860 --> 00:18:50,540 Those were the last few lines of code 355 00:18:50,540 --> 00:18:52,770 in the pseudocode that we saw. 356 00:18:52,770 --> 00:18:55,970 And for each edge from U to V, 357 00:18:55,970 --> 00:18:57,920 if the distance to V is greater 358 00:18:57,920 --> 00:19:00,240 than the sum of the distance to U 359 00:19:00,240 --> 00:19:02,570 plus the edge weight from U to V, 360 00:19:02,570 --> 00:19:04,710 then we know we have a negative cycle. 361 00:19:04,710 --> 00:19:06,823 Let's take a look and see how that works. 362 00:19:08,470 --> 00:19:11,040 So here we have a very simple graph 363 00:19:11,040 --> 00:19:14,410 on three nodes: A, B, and C. 364 00:19:14,410 --> 00:19:18,730 And you can see in the left-hand example here 365 00:19:18,730 --> 00:19:21,690 that we have a negative cycle weight. 366 00:19:21,690 --> 00:19:24,790 So we have three plus two minus seven 367 00:19:24,790 --> 00:19:27,163 gives us a negative two cycle weight. 368 00:19:28,060 --> 00:19:32,670 And to run Bellman-Ford, we have three nodes 369 00:19:32,670 --> 00:19:34,893 so we're gonna need to run two iterations. 370 00:19:36,580 --> 00:19:40,060 And we initialize our values, this is our starting node 371 00:19:40,060 --> 00:19:41,270 so we set that to zero. 372 00:19:41,270 --> 00:19:45,800 We set these to infinity, and then we run our algorithm. 373 00:19:45,800 --> 00:19:50,800 And so we go from A to C and we find this path to C 374 00:19:53,440 --> 00:19:57,620 from A of weight two, and then we go from C to B 375 00:19:57,620 --> 00:20:02,620 and we find this path here of weight negative five 376 00:20:03,100 --> 00:20:06,960 which is two minus seven from C. 377 00:20:06,960 --> 00:20:10,310 And then we go from B to A 378 00:20:10,310 --> 00:20:12,910 and we discover a path to A 379 00:20:12,910 --> 00:20:16,340 that's negative five plus three is negative two. 380 00:20:16,340 --> 00:20:19,610 Of course, that's our cycle weight. 381 00:20:19,610 --> 00:20:22,330 And you notice that we've discovered a path. 382 00:20:22,330 --> 00:20:25,680 The shortest path to A is not just to stay put at A, 383 00:20:25,680 --> 00:20:29,560 but actually to go around this negative cycle 384 00:20:29,560 --> 00:20:34,050 and now we have a distance of negative two from A to itself. 385 00:20:34,050 --> 00:20:37,280 And that's really at the root of the problem here. 386 00:20:37,280 --> 00:20:39,080 If we do this again, 387 00:20:39,080 --> 00:20:41,730 remember we're starting from these points here 388 00:20:41,730 --> 00:20:46,080 so negative two plus two gives us zero from A 389 00:20:46,080 --> 00:20:50,120 and then we get negative seven from C 390 00:20:50,120 --> 00:20:53,900 and then negative seven plus three is negative four from B 391 00:20:53,900 --> 00:20:56,710 and of course the cycle weight is negative two 392 00:20:56,710 --> 00:20:59,560 so we've gone from zero to negative two to negative four. 393 00:21:00,880 --> 00:21:03,740 So now we perform this check to see 394 00:21:05,410 --> 00:21:10,410 if we have a negative cycle and you can see here right away 395 00:21:10,500 --> 00:21:13,973 that we have negative four here plus two. 396 00:21:16,370 --> 00:21:19,120 Zero is greater than that value. 397 00:21:19,120 --> 00:21:21,440 Negative four plus two is negative two, 398 00:21:21,440 --> 00:21:24,050 zero is greater than negative two. 399 00:21:24,050 --> 00:21:25,420 And so right here, 400 00:21:25,420 --> 00:21:29,050 we see this is the edge that violates that condition 401 00:21:29,050 --> 00:21:31,230 and we know we have a negative cycle. 402 00:21:31,230 --> 00:21:33,650 And so this is how we detect negative cycles 403 00:21:33,650 --> 00:21:35,260 in the Bellman-Ford algorithm. 404 00:21:35,260 --> 00:21:36,730 So at this point, 405 00:21:36,730 --> 00:21:39,780 Bellman-Ford would return an error telling us 406 00:21:39,780 --> 00:21:43,053 that it had found a negative cycle in our graph. 407 00:21:44,130 --> 00:21:49,130 So that sums up the major differences 408 00:21:50,210 --> 00:21:54,060 between Bellman-Ford and Dijkstra. 409 00:21:54,060 --> 00:21:56,750 And again, if you know 410 00:21:56,750 --> 00:21:59,420 you have all non-negative edge weights, 411 00:21:59,420 --> 00:22:02,440 use Dijkstra because it's much more efficient, 412 00:22:02,440 --> 00:22:04,960 but if you do have negative edge weights 413 00:22:04,960 --> 00:22:08,713 and no negative cycles, then Bellman-Ford is the way to go. 414 00:22:09,880 --> 00:22:11,030 And that wraps this up.