1 00:00:00,000 --> 00:00:04,145 Now that we understand the optimal substructure present in shortest paths, 2 00:00:04,145 --> 00:00:08,291 we can follow our usual dynamic programming recipe to arrive at the basic 3 00:00:08,291 --> 00:00:13,777 version of the Bellman-Ford algorithm. Let's compile our optimal substructure 4 00:00:13,777 --> 00:00:19,089 lemma into a recurrence of formula that says how the optimal solution of a given 5 00:00:19,089 --> 00:00:23,060 sub problem depends on that of smaller sub problems. 6 00:00:23,060 --> 00:00:28,505 I'll use the notation capital L sub I V to denote the optimal solution value of 7 00:00:28,505 --> 00:00:32,726 the corresponding subproblem. Subproblems being indexed by two 8 00:00:32,726 --> 00:00:38,103 parameters, one V, that's the destination we're interested in, in this subproblem. 9 00:00:38,103 --> 00:00:43,481 In the second one is the budget I on the number of edges that are permitted in 10 00:00:43,481 --> 00:00:46,924 paths from S to V in this subproblem. So, a few details. 11 00:00:46,924 --> 00:00:51,277 First of all, remember that in the last video we proved the optimal substructure 12 00:00:51,277 --> 00:00:55,358 limit in general for general graph G, which may indeed have negative cycles. 13 00:00:55,358 --> 00:00:59,166 For that reason, we have to allow cycles in shortest paths from S to V. 14 00:00:59,166 --> 00:01:03,464 We're not concerned about the cycle being traverse an infinite number of times, 15 00:01:03,464 --> 00:01:07,600 because we have this finite budget I and the number of edges that we permit. 16 00:01:08,740 --> 00:01:13,649 I also need to explain what I mean in the case that there are no paths from S to V 17 00:01:13,649 --> 00:01:18,499 within most I edges, and indeed when I is very small, that will in fact be the case 18 00:01:18,499 --> 00:01:23,230 for many destinations V, so if there's no way to get from S to V using I hops, we 19 00:01:23,230 --> 00:01:28,701 just define LIV to be plus infinity. And as usual, in the recurrence which is 20 00:01:28,701 --> 00:01:33,345 going to be defined for every positive integer I and every possible destination 21 00:01:33,345 --> 00:01:37,524 V we're just going to state that the optimal solution value for the sub 22 00:01:37,524 --> 00:01:41,761 problem is the best of the possible candidates identified in the optimal 23 00:01:41,761 --> 00:01:45,011 substructure lemma. That is, capital L sub IV, the optimal 24 00:01:45,011 --> 00:01:49,712 solution value for the sub-problem with parameters I and V is the best of all of 25 00:01:49,712 --> 00:01:53,021 the possibilities. So let me start with a minimum to take 26 00:01:53,021 --> 00:01:57,300 the best of the case one candidate and the case two candidate. 27 00:01:57,300 --> 00:02:03,042 The case one candidate is simple enough. One option is always just to inherit the 28 00:02:03,042 --> 00:02:08,080 best path we found from s to v that uses only I-1 edges or less. 29 00:02:08,080 --> 00:02:13,527 In case two, you'll recall from the quiz at the end of the last video really 30 00:02:13,527 --> 00:02:18,617 comprises a number of sub cases, one for each choice of the finally hop. 31 00:02:18,617 --> 00:02:24,064 So here we're going to have another minimum ranging over all possible edges 32 00:02:24,064 --> 00:02:26,723 WV. For a given choice of that last hop. 33 00:02:26,723 --> 00:02:31,529 The shortest path length is going to be the shortest path from s to that choice 34 00:02:31,529 --> 00:02:34,053 of w that uses the most I minus one edges. 35 00:02:34,053 --> 00:02:39,540 And then of course we also we incur the edge cost of the final hop, w comma v. 36 00:02:39,540 --> 00:02:43,904 Correctness, as usual, follows immediately from the optimal substructure 37 00:02:43,904 --> 00:02:46,610 lemma. We know these are the only candidates, 38 00:02:46,610 --> 00:02:50,360 and by the definition of the recurrence, we pick the best one. 39 00:02:50,360 --> 00:02:53,741 Because the optimal substructure lemma has been proven. 40 00:02:53,741 --> 00:02:58,229 Whether or not g has a negative cycle, this recurrence is correct for all 41 00:02:58,229 --> 00:03:01,856 positive values of I, whether or not g has a negative cycle. 42 00:03:01,856 --> 00:03:06,467 So now, let's see how it's useful to assume that the input graph g does not 43 00:03:06,467 --> 00:03:11,455 have a negative cycle. So we had a quiz not too long ago, that 44 00:03:11,455 --> 00:03:15,030 discussed the use of the no negative cycles hypothesis. 45 00:03:15,030 --> 00:03:20,165 In particular, we argued that N-1 edges are always enough to capture a shortest 46 00:03:20,165 --> 00:03:23,025 path, between S and any possible destination. 47 00:03:23,025 --> 00:03:25,885 Why? Well, suppose there's no negative cycles, 48 00:03:25,885 --> 00:03:29,969 picks a destination V, show me a path that has at least N edges. 49 00:03:29,969 --> 00:03:34,495 If it has at least N edges, then it visits at least N plus one vertices. 50 00:03:34,495 --> 00:03:38,638 There's only N vertices, so the path must visit some vertex twice, 51 00:03:38,638 --> 00:03:43,737 and in between two consecutive visits of a given vertex that's a directed cycle. 52 00:03:43,737 --> 00:03:47,195 My hypothesis? There are no negative directed cycles, 53 00:03:47,195 --> 00:03:51,925 they're all non negative. So if I throw out this directed cycle from this path, I 54 00:03:51,925 --> 00:03:56,595 get a new path to the same destination V and it's overall length has only gone 55 00:03:56,595 --> 00:03:58,959 down. Discarding cycles only makes paths 56 00:03:58,959 --> 00:04:03,334 shorter. That's why there's a shortest path with, with no repeated vertices, 57 00:04:03,334 --> 00:04:08,841 that is with at most n minus one edges. So what does this observation have to do 58 00:04:08,841 --> 00:04:12,411 with our recurrence? Well it tells us, when you only need to 59 00:04:12,411 --> 00:04:17,192 compute the end recurrence, evaluate sub problems for values of I up to n minus 60 00:04:17,192 --> 00:04:19,975 one. There is no point in giving a sub problem 61 00:04:19,975 --> 00:04:24,272 a budget bigger than n minus one edges if there are no negative cycles. 62 00:04:24,272 --> 00:04:28,326 It's not going to be useful. You're guaranteed to have already found 63 00:04:28,326 --> 00:04:32,260 the shortest path by the time I has gone as large as n minus one. 64 00:04:34,000 --> 00:04:37,792 So, to make sure this point is clear, let me just formally write down the 65 00:04:37,792 --> 00:04:42,112 subproblems that we're going to solve in the Bellman-Ford algorithm, and which are 66 00:04:42,112 --> 00:04:46,221 going to be sufficient to correctly compute shortest paths for input graph g 67 00:04:46,221 --> 00:04:51,688 that do not have negative cycles. The subproblems are simply to compute the 68 00:04:51,688 --> 00:04:56,434 shortest path links capital L sub of IV. Of course, for all destinations, we're 69 00:04:56,434 --> 00:05:01,057 responsible for ultimately computing shortest paths to every destination V, 70 00:05:01,057 --> 00:05:04,139 and for all relevant choices of the edge budget I. 71 00:05:04,139 --> 00:05:09,194 And so the base case is going to be when I equals zero, and we just said it has to 72 00:05:09,194 --> 00:05:13,620 go up as n minus 1, and no further. And this is actually a pleasingly 73 00:05:13,620 --> 00:05:17,943 parsimonious collection of sub-problems. It may strike you actually kind of a lot, 74 00:05:17,943 --> 00:05:22,046 because there is a quadratic number, or there's N choices for the destination V, 75 00:05:22,046 --> 00:05:24,673 and then I is rank taking on N different values. 76 00:05:24,673 --> 00:05:28,612 But remember, unlike all the other problems we've been talking about, the 77 00:05:28,612 --> 00:05:32,990 output of this problem is linear size. We're suppose to output a number for each 78 00:05:32,990 --> 00:05:35,890 destination V. So, we really only have a linear number 79 00:05:35,890 --> 00:05:39,556 of sub-problems for each statistic we're responsible for computing, 80 00:05:39,556 --> 00:05:43,660 and that's as good as we've had on any of our other programming algorithms. 81 00:05:45,080 --> 00:05:50,091 So now it's a simple matter to write out the pseudo-code of the justifiably famous 82 00:05:50,091 --> 00:05:54,952 Bellman-Ford algorithm Because there are subproblems that are indexed by two 83 00:05:54,952 --> 00:05:58,861 parameters, the edge budget I and the decimation V, we are going to have a 84 00:05:58,861 --> 00:06:03,145 two-dimension array A. Remember that we're measuring sub-problem 85 00:06:03,145 --> 00:06:06,688 size via the edge budget I. That's sort of the great idea in the 86 00:06:06,688 --> 00:06:11,559 Bellman-Ford algorithm, to introduce this edge budget to control sub-problem size. 87 00:06:11,559 --> 00:06:15,711 So the base case is when I equals zero, and then we're talking about getting from 88 00:06:15,711 --> 00:06:19,863 S to some vertex V, using zero edges. Okay, well if V happens to equal S, then 89 00:06:19,863 --> 00:06:24,015 you can do it with the empty path, and the length of the empty path is zero. 90 00:06:24,015 --> 00:06:28,167 But if V is any vertex other than S, then, of course, you can't get from S to 91 00:06:28,167 --> 00:06:30,880 V using zero edges, and remember in that case, 92 00:06:30,880 --> 00:06:34,880 we define the optimum value solution to be plus infinity. 93 00:06:36,260 --> 00:06:40,508 So now we move onto are customary double four-loop, one four-loop for each of the 94 00:06:40,508 --> 00:06:44,370 indices that a nexus R array A. But actually, what's interesting is 95 00:06:44,370 --> 00:06:48,563 unlike most of the dynamic programming algorithms we're discussing, here the 96 00:06:48,563 --> 00:06:51,819 order of the four-loop matters. You can not pick arbitrarly. 97 00:06:51,819 --> 00:06:56,122 You really need to make sure that you have all the smaller subproblems solved 98 00:06:56,122 --> 00:06:59,819 by the time you need them. That means the outer four-loop should be 99 00:06:59,819 --> 00:07:04,501 indexed by the subproblem size I. So, as we discussed, we're not going to 100 00:07:04,501 --> 00:07:08,604 bother letting I range above n minus one. That's going to be sufficient for in the 101 00:07:08,604 --> 00:07:12,658 case where there are no negative cycles, and for each choice of I, we solve all of 102 00:07:12,658 --> 00:07:15,160 the corresponding sub problems, all destinations v. 103 00:07:16,200 --> 00:07:21,877 For each choice of I and V, of course, we just write down in code the formula that 104 00:07:21,877 --> 00:07:26,443 we stated in the recurrence. So as I'm sure you recall, case one 105 00:07:26,443 --> 00:07:31,037 furnishes one possible candidate. It's always an option to just inheret, the 106 00:07:31,037 --> 00:07:35,018 shortest path from S to V that you computed using only, I-1 edges. 107 00:07:35,018 --> 00:07:40,102 Alternatively from case two, there's also one candidate furnished for each twist of 108 00:07:40,102 --> 00:07:44,696 the final hop, so for each edge, that ends at V, for each choice W comma V, 109 00:07:44,696 --> 00:07:49,045 there's an option of taking a shortest path from S to W, that uses only, I minus 110 00:07:49,045 --> 00:07:52,520 1 edges, and tacking on that final edge, WV. 111 00:07:52,520 --> 00:07:58,151 And as we've discussed, if it just so happens that the input graph G has no 112 00:07:58,151 --> 00:08:04,308 negative cycles, then this algorithm will indeed terminate with a correct shortest 113 00:08:04,308 --> 00:08:10,240 path from S to all of the destinations. Those answers will be lying in wait for 114 00:08:10,240 --> 00:08:14,080 you, in the biggest subproblems, the A N minus 1 V's. 115 00:08:14,080 --> 00:08:17,720 So that's correctness as usual. It follows primarily from the optimal 116 00:08:17,720 --> 00:08:21,835 substructure lemma, but in this case also the hypothesis of no negative cycles 117 00:08:21,835 --> 00:08:26,003 guarantees that taking I equal N minus one is large enough to actually capture 118 00:08:26,003 --> 00:08:29,063 the final answers. So we'll talk about the running time of 119 00:08:29,063 --> 00:08:33,072 the Bellman-Ford algorithm in a sec, but first let's just go through a quick 120 00:08:33,072 --> 00:08:35,447 example to make sure all of this makes sense.