1 00:00:00,000 --> 00:00:03,734 So now let's compile the optimal substructure we just identified on 2 00:00:03,734 --> 00:00:08,388 all-pairs shortest paths into a dynamic programming algorithm and this would be 3 00:00:08,388 --> 00:00:11,961 the Floyed-Warshall Algorithm. Let me begin with a quiz and ask you to 4 00:00:11,961 --> 00:00:16,370 sort out the base cases. So remember our subproblems actually have 5 00:00:16,370 --> 00:00:18,949 three indices. The first index is the origin i, the 6 00:00:18,949 --> 00:00:23,023 second index is the destination j, and then there's our budget k which controls 7 00:00:23,023 --> 00:00:27,252 which of the vertices were permitted to use as internal nodes in a shortest path 8 00:00:27,252 --> 00:00:30,295 in the subproblem. So because of these three indices, we're 9 00:00:30,295 --> 00:00:32,307 going to be using a three-dimensional array A. 10 00:00:33,440 --> 00:00:37,608 So the plan, of course, is to solve systematically all of these subproblems 11 00:00:37,608 --> 00:00:42,058 where the subproblem corresponding to a choice of i, j, and k is just the length 12 00:00:42,058 --> 00:00:46,339 of the shortest path, starting at i ending at j, and using intermediate nodes 13 00:00:46,339 --> 00:00:51,099 only labeled 1 through k. And what's cool about these definitions 14 00:00:51,099 --> 00:00:55,308 is it's clear which are the bigger subproblems and which are the sub, 15 00:00:55,308 --> 00:00:59,090 smaller subproblems. That's controlled completely by the index 16 00:00:59,090 --> 00:01:01,346 k. So the smallest set of subproblems, 17 00:01:01,346 --> 00:01:05,128 the ones where we have to think through the base case is when k0. 18 00:01:05,128 --> 00:01:07,690 = 0. So the quiz asks you, how should we fill 19 00:01:07,690 --> 00:01:12,264 in A[i,j,0] for all of the various choices of origin i and the destination 20 00:01:12,264 --> 00:01:14,704 j? And as usual, if there are no feasible 21 00:01:14,704 --> 00:01:17,815 solutions. If no paths from i to j make use only of 22 00:01:17,815 --> 00:01:21,780 internal nodes 1 through k, then we define this to be plus infinity. 23 00:01:27,100 --> 00:01:34,197 Actually, the correct answer is c. So if i and j are the same, then, there 24 00:01:34,197 --> 00:01:37,860 is a path that starts at i ends at j, the empty path. 25 00:01:37,860 --> 00:01:42,248 It does in fact have no internal nodes at all and it has length: zero. 26 00:01:42,248 --> 00:01:47,278 [SOUND] Similarly if i and j are directly connected and we look only at paths that 27 00:01:47,278 --> 00:01:51,701 have no internal nodes whatsoever, well then, we're stuck with the cost of 28 00:01:51,701 --> 00:01:56,003 whatever the direct edge from i to j is, so we just fill it in with cij. 29 00:01:56,003 --> 00:02:00,245 On the other hand, if i is not equal to j, and i and j are not directly 30 00:02:00,245 --> 00:02:04,972 connected, then every path from i to j has at least one internal node, so there 31 00:02:04,972 --> 00:02:08,123 are no paths from i to j without any internal nodes. 32 00:02:08,123 --> 00:02:11,880 In that case, by definition, we assign a value of plus infinity. 33 00:02:13,280 --> 00:02:16,999 So having figured out the base cases, it's now a simple matter to write out the 34 00:02:16,999 --> 00:02:20,435 full blown Floyed-Warshall algorithm. In the past, I've been writing down a 35 00:02:20,435 --> 00:02:23,872 recurrence as an intermediate step. I think I'm going to skip that step here, 36 00:02:23,872 --> 00:02:27,356 we have so much practice with it. I think we can just jump straight to the 37 00:02:27,356 --> 00:02:29,192 code. And in the code, we will solve the 38 00:02:29,192 --> 00:02:32,864 problem systematically, from the smaller values of k to the bigger values of k. 39 00:02:32,864 --> 00:02:36,442 And each time we solve a subproblem, we are just going to do brute-force search 40 00:02:36,442 --> 00:02:40,114 amongst the two possibilities that we identified in the optimal substructure 41 00:02:40,114 --> 00:02:42,313 lemma. So we have our three-dimensional array A 42 00:02:42,313 --> 00:02:46,000 and it's three dimensional, because we have three indices for our subproblems. 43 00:02:46,000 --> 00:02:49,495 We gotta know what the origin is, we gotta know what the destination j is. 44 00:02:49,495 --> 00:02:53,039 And we gotta know how big a prefix k of vertices we have to work with for 45 00:02:53,039 --> 00:02:57,108 internal nodes in our paths. The base case [INAUDIBLE] was when K 46 00:02:57,108 --> 00:03:01,294 equals zero, so we just fill that in in a pre-processing step according to the quiz 47 00:03:01,294 --> 00:03:05,071 we just solved. And now we have our triple for loop. 48 00:03:05,071 --> 00:03:09,885 One for loop for each of the indices. Now, as always it's important, we solve 49 00:03:09,885 --> 00:03:14,700 the smallest subproblems first. The subproblem size is controlled by k so 50 00:03:14,700 --> 00:03:17,460 we better put k as the outermost for loop. 51 00:03:17,460 --> 00:03:21,120 The order of i and j is irrelevant, but k better go first. 52 00:03:23,440 --> 00:03:27,291 [SOUND] So to compute the value of a given subproblem, A, i, j, k, we just 53 00:03:27,291 --> 00:03:31,597 take the better, that is the minimum of the two candidates identified in our 54 00:03:31,597 --> 00:03:35,449 optimal substructure lemma. The first candidate furnished by k is one 55 00:03:35,449 --> 00:03:40,037 is just to inherit the solution computed in the last iteration of the outer for 56 00:03:40,037 --> 00:03:45,317 loop, that is i,j,k - 1. So the second candidate is provided by 57 00:03:45,317 --> 00:03:49,171 the second case of the optimal substructure lemma, this is where in the 58 00:03:49,171 --> 00:03:52,971 optimal solution to the current subproblem, we actually do use node k 59 00:03:52,971 --> 00:03:56,934 internally on the shortest path. In that case, we know what it has to look 60 00:03:56,934 --> 00:04:01,060 like, we have to just be taking the optimal solution from the last iteration 61 00:04:01,060 --> 00:04:04,914 of the outer for loop from i to k, and then catenating that with, that is 62 00:04:04,914 --> 00:04:09,365 adding to it the length of the shortest path computed last iteration of the outer 63 00:04:09,365 --> 00:04:14,878 for loop from k to j. So notice that our code does indeed pass 64 00:04:14,878 --> 00:04:18,283 the sanity check, you should always use when we evaluate a subproblem. 65 00:04:18,283 --> 00:04:22,444 We already have the solutions to all of the relevant subproblems available for 66 00:04:22,444 --> 00:04:25,613 constant-time lookup, that's because all of them were computed and the last 67 00:04:25,613 --> 00:04:29,207 interation of the outer for loop. There's also not a whole lot to say about 68 00:04:29,207 --> 00:04:32,375 the correctness or the running time. Correctness is the usual story. 69 00:04:32,375 --> 00:04:35,543 The only nontrivial work is in the optimal substructure lemma that 70 00:04:35,543 --> 00:04:39,042 identifies the only possible two candidates for the optimal solution to a 71 00:04:39,042 --> 00:04:41,407 subproblem. We're systemically solving all of them 72 00:04:41,407 --> 00:04:43,960 taking the better of the two only possible candidates. 73 00:04:43,960 --> 00:04:46,940 As far as the running time? Well, how many subproblems are there? 74 00:04:46,940 --> 00:04:49,748 Pretty easier to see, each of our three for loops takes on n 75 00:04:49,748 --> 00:04:52,610 different values, so that's n^3 subproblems overall. 76 00:04:52,610 --> 00:04:56,140 Pretty clear that we only do a constant amount of work per subproblem, 77 00:04:56,140 --> 00:05:01,676 that gives us the cubic running time. So, let me wrap up the discussion of 78 00:05:01,676 --> 00:05:06,585 Floyed-Warshall algorithm with a couple odds and ends, answers to two frequently 79 00:05:06,585 --> 00:05:10,153 asked questions. So question number one, which frankly I 80 00:05:10,153 --> 00:05:13,796 kind of hope you're wondering about, is well, what's up with the input graphs 81 00:05:13,796 --> 00:05:16,983 that do have a negative cost cycle? Let's recap what we've done. 82 00:05:16,983 --> 00:05:20,727 We stated and proved the optimal substructure lemma, only for input graphs 83 00:05:20,727 --> 00:05:24,674 that do not have a negative cost cycle. Our correctness argument for the 84 00:05:24,674 --> 00:05:27,861 Floyed-Warshall algorithm relied on the correctness of the recurrence, 85 00:05:27,861 --> 00:05:31,453 which in turn relies on the correctness of the optimal substructure lemma. 86 00:05:31,453 --> 00:05:35,009 So, if you feed in some arbitrary graph to the Floyed-Warshall algorithm, it 87 00:05:35,009 --> 00:05:37,219 might have a negative cost cycle, it might not. 88 00:05:37,219 --> 00:05:40,438 Well, the algorithm's just going to process its n^3 iterations and fill in 89 00:05:40,438 --> 00:05:44,379 this three-dimensional array either way. So you're left at the end of the day with 90 00:05:44,379 --> 00:05:47,935 this 3D array filled with numbers. And if it just so happened there was no 91 00:05:47,935 --> 00:05:51,635 negative cost cycle on the input graph, then, you know that the final batch of 92 00:05:51,635 --> 00:05:54,614 numbers when kN = n are, in fact, the correct shortest path distances. 93 00:05:54,614 --> 00:05:57,834 But how do you know if the input graph had a negative cycle or not? 94 00:05:57,834 --> 00:06:02,680 How do you know whether you can trust this last batch of numbers when k = n? 95 00:06:04,020 --> 00:06:08,909 Well, there's actually a very sleek answer to this question which is, all you 96 00:06:08,909 --> 00:06:13,734 need to do is scan the diagonal of the numbers computed in the final round. 97 00:06:13,734 --> 00:06:18,881 If the input graph does have a negative cost cycle, then for at least one vertex 98 00:06:18,881 --> 00:06:21,969 i, you will see a negative number in the entry A(i,i,n). 99 00:06:24,540 --> 00:06:27,222 So let's assume for the moment that this fact is true, 100 00:06:27,222 --> 00:06:31,245 that negative cost cycles will show up in diagonal in the final round of entries. 101 00:06:31,245 --> 00:06:34,921 Then, I hope it's clear how you can use the Floyed-Warshall algorithm to solve 102 00:06:34,921 --> 00:06:37,901 the general version of the all-pairs shortest paths problem. 103 00:06:37,901 --> 00:06:41,080 Whereby, the general version I mean, you're given an input graph, 104 00:06:41,080 --> 00:06:43,315 it may or may not have a negative cost cycle. 105 00:06:43,315 --> 00:06:46,990 And, you have to do one of two things, either you correctly deduce that the 106 00:06:46,990 --> 00:06:50,120 input graph has a negative cost cycle, then you're off the hook. 107 00:06:50,120 --> 00:06:53,890 Or, you compute correct shortest paths between all pairs of vertices. 108 00:06:53,890 --> 00:06:57,661 [SOUND] So the way you use that using Floyed-Warshall, you just take the input 109 00:06:57,661 --> 00:07:00,594 graph, you just run the algorithm, the n^3 iterations. 110 00:07:00,594 --> 00:07:03,527 You scan the diagonal. You scan A(i,i,n) for all values of i. 111 00:07:03,527 --> 00:07:06,565 If you see a negative number, you say, oop, I'm off the hook, 112 00:07:06,565 --> 00:07:08,451 there's a negative cost cycle. Sorry. 113 00:07:08,451 --> 00:07:14,280 [SOUND] And if the diagonal is all zeros, then you return the final batch of 114 00:07:14,280 --> 00:07:17,940 A(i,j,n) as the correct shortest path distances. 115 00:07:19,320 --> 00:07:22,710 I'm not going to prove this formally. I'll leave that for you to do in the 116 00:07:22,710 --> 00:07:25,766 privacy of your own home. But let me just suggest some intuition 117 00:07:25,766 --> 00:07:27,820 about why you would expect this to be true. 118 00:07:29,100 --> 00:07:32,956 So, suppose the input graph does, indeed, have a negative cost cycle. 119 00:07:32,956 --> 00:07:36,580 Pick some arbitrary vertex on that cycle, let's say a vertex x. 120 00:07:36,580 --> 00:07:40,904 Define vertex y to be the highest label of some other vertex on the cycle. 121 00:07:40,904 --> 00:07:45,345 Now, think about the following points in the Floyed-Warshall algorithm and its 122 00:07:45,345 --> 00:07:48,735 triple for loop. Think about when the outer iteration, the 123 00:07:48,735 --> 00:07:52,124 value of k is equal to y. So for the first time, the vertex y is 124 00:07:52,124 --> 00:07:56,200 eligible to be on internal nodes of shortest paths. 125 00:07:56,200 --> 00:08:00,938 And think of that in the inner for loops, when both i and j are equal to x. 126 00:08:00,938 --> 00:08:04,887 So, what is the recurrence or what is the formula the Floyed-Warshall is going to 127 00:08:04,887 --> 00:08:07,652 say? It's going to fill in this particular 128 00:08:07,652 --> 00:08:14,521 subproblem value, that is capital A(x,x,y) the minimum of two things. 129 00:08:14,521 --> 00:08:19,260 So first of all A(x,x,y - 1). Who knows what that is? 130 00:08:19,260 --> 00:08:24,696 But the second candidate, this is the interesting one, one candidate to fill in 131 00:08:24,696 --> 00:08:30,315 this entry will be A(x,y,y - 1) + A(y,x,y - 1). 132 00:08:30,315 --> 00:08:36,024 That is one of the candidates for the entry in this diagonal, A(x,x,y) will be 133 00:08:36,024 --> 00:08:41,457 the link of the shortest path from x to y whose all internal nodes are less than y 134 00:08:41,457 --> 00:08:46,890 plus the link of a shortest path from y back to x whose internal nodes are all 135 00:08:46,890 --> 00:08:50,398 less than y. Well, two candidates for such paths are 136 00:08:50,398 --> 00:08:53,823 the two halves of this cycle. Right y we chose to be the largest 137 00:08:53,823 --> 00:08:57,585 indexed node anywhere on the cycle, all the other vertices other than x and y 138 00:08:57,585 --> 00:09:00,858 have only smaller indices, so they are permissible internal nodes at 139 00:09:00,858 --> 00:09:04,033 the previous iteration. So if you take the sum of these two paths 140 00:09:04,033 --> 00:09:06,915 that's just a cycle length which by assumption is negative. 141 00:09:06,915 --> 00:09:10,774 So at this point in the Floyed-Warshall algorithm, if not earlier, when the outer 142 00:09:10,774 --> 00:09:14,585 for loop k is equal to y and when the looking from x back to x itself, at that 143 00:09:14,585 --> 00:09:18,297 point, we'll get a negative number. And because these numbers only go down in 144 00:09:18,297 --> 00:09:22,547 future iterations of the outer for loop, that negative number will persist to the 145 00:09:22,547 --> 00:09:25,185 end of the algorithm. That's why, to check for negative cycle, 146 00:09:25,185 --> 00:09:29,016 just scan the diagonal of the final batch of numbers that tells you whether or not 147 00:09:29,016 --> 00:09:36,741 there was one in the input graph. So, the second frequently asked question 148 00:09:36,741 --> 00:09:39,987 concerns reconstruction. Suppose after you run Floyed-Warshall, 149 00:09:39,987 --> 00:09:43,852 you actually want to know the actual sequence of edges that's the shortest 150 00:09:43,852 --> 00:09:48,380 path from some, your favorite origin i and your favorite destination j. 151 00:09:48,380 --> 00:09:51,466 So, like in the Bellman-Ford reconstruction solution, we're going to 152 00:09:51,466 --> 00:09:53,781 have to store a little bit of extra information, 153 00:09:53,781 --> 00:09:56,096 a constant amount of information per subproblem. 154 00:09:56,096 --> 00:09:59,713 Now, in the Bellman-Ford algorithm, we only had one subproblem per choice of 155 00:09:59,713 --> 00:10:01,256 desination, the source was fixed. 156 00:10:01,256 --> 00:10:05,211 And for each choice of a destination, we remembered the penultimate vertex on a 157 00:10:05,211 --> 00:10:08,587 shortest path to that destination. So for Floyd-Warshall, the number of 158 00:10:08,587 --> 00:10:11,046 subproblems is indexed by origins and destinations. 159 00:10:11,046 --> 00:10:14,422 And so, for each choice of an origin and destination, we're, again, going to 160 00:10:14,422 --> 00:10:16,640 remember some other vertex on a shortest path. 161 00:10:16,640 --> 00:10:19,679 But, the vertex we remember might not be the second to last one. 162 00:10:19,679 --> 00:10:23,657 It might not be the last top. Rather, what we're going to remember is 163 00:10:23,657 --> 00:10:29,620 the highest index vertex on a shortest path from i to j. 164 00:10:30,980 --> 00:10:34,683 So I'm going to call this additional information a two-dimensional array B, 165 00:10:34,683 --> 00:10:38,901 this is indexed just by the choice of the origin, by the choice of the destination. 166 00:10:38,901 --> 00:10:42,861 And again, the semantics is we want the i, j entry of this array to be the max 167 00:10:42,861 --> 00:10:45,536 label of any internal node on the shortest i, j path. 168 00:10:45,536 --> 00:10:49,703 So two things we have to understand are, first of all, how do we compute all these 169 00:10:49,703 --> 00:10:53,200 B(i,j) values on the forward-pass of the Floyed-Warshall algorithm without 170 00:10:53,200 --> 00:10:56,647 affecting its running time? Secondly, if we successfully compute all 171 00:10:56,647 --> 00:11:00,967 of these B(i,j) on the forward pass, how do we reconstruct shortest paths by going 172 00:11:00,967 --> 00:11:04,311 backward through the filled in table? So this is all analogous to Bellman-Ford 173 00:11:04,311 --> 00:11:08,304 and Bellman-Ford. We two that on the forward pass, you could maintain the 174 00:11:08,304 --> 00:11:12,245 predecessor point it wasn't a big deal, just when you fill in, when you recompute 175 00:11:12,245 --> 00:11:15,569 shortest pass in a given round of subproblems. If you compute some new 176 00:11:15,569 --> 00:11:18,703 shortest path value, i.e. you don't just inherit that solution from 177 00:11:18,703 --> 00:11:22,455 the previous round, you just figure out which vertex was responsible for it and 178 00:11:22,455 --> 00:11:26,159 you remember that as your predecessor. And then given the predecessor pointers 179 00:11:26,159 --> 00:11:29,768 are correctly computed, you just trace back pointers to reconstruct shortest 180 00:11:29,768 --> 00:11:31,905 paths. So here, how do you compute them on the 181 00:11:31,905 --> 00:11:36,084 forward direction? Well, remember in the, in the recurrence 182 00:11:36,084 --> 00:11:39,277 that we used to fill in the three-dimensional array, A, 183 00:11:39,277 --> 00:11:43,086 there's two possibilities, either you just inherit the solution from 184 00:11:43,086 --> 00:11:46,278 the previous iteration, that's kind of the boring case. 185 00:11:46,278 --> 00:11:50,703 And the interesting case is when you actually use the newly available vertex k 186 00:11:50,703 --> 00:11:54,680 in the shortest path from i to j. So whenever you use that second case of 187 00:11:54,680 --> 00:11:58,433 the recurrence to reset the value in the three dimensional array A. 188 00:11:58,433 --> 00:12:02,186 At that point, you reset the corresponding B(i,j) value to the current 189 00:12:02,186 --> 00:12:05,379 value of k. So that is, just add the forward pass of 190 00:12:05,379 --> 00:12:07,900 Floyd-Warshall. You always remember the last vertex 191 00:12:07,900 --> 00:12:13,600 responsible for changing your shortest path distance between i and j. 192 00:12:13,600 --> 00:12:17,716 So now, let's suppose you've coded up this extension of the forward pass of 193 00:12:17,716 --> 00:12:20,664 Floyed-Warshall correctly, so that at the end of your triple for 194 00:12:20,664 --> 00:12:24,018 loop, you have accurate computations of all of these B(i,j) values. 195 00:12:24,018 --> 00:12:27,169 That is, for any origin and desination, you have a little birdy, 196 00:12:27,169 --> 00:12:30,930 the two-dimensional array, B, that will just tell you in constant time what is 197 00:12:30,930 --> 00:12:33,674 the max labeled vertex internal on a shortest i, j path? 198 00:12:33,674 --> 00:12:36,724 Well, maybe you really want to, know your favorite source is 23. 199 00:12:36,724 --> 00:12:41,247 Your favorite destination is 17 and you want to reconstruct a shortest path from 200 00:12:41,247 --> 00:12:45,363 your oracles, your filled in tables. So you look in to the entry 23, 17 into 201 00:12:45,363 --> 00:12:47,345 the B array. You have this little birdy, 202 00:12:47,345 --> 00:12:51,155 this filled in table tells you the max labelled vertex on a shortest path 203 00:12:51,155 --> 00:12:54,402 between 23 and 17. Maybe it tells you it's the vertex 43. 204 00:12:54,402 --> 00:12:58,989 So it promises you that the shortest path comprises 23 on one end, 17 on the other 205 00:12:58,989 --> 00:13:02,184 end, a bunch of stuff in the middle, the largest of which is 43. 206 00:13:02,184 --> 00:13:06,101 Well, you like, okay cool, let me just, now I know where the shortest has to be. 207 00:13:06,101 --> 00:13:10,584 It's the shortest path from 23 to 43 plus a shortest path from 43 to 17, and you 208 00:13:10,584 --> 00:13:14,604 just reconstruct those two shortest paths recursively in exactly the same way. 209 00:13:14,604 --> 00:13:18,881 This has got to terminate because at the end of the day the shortest path is 210 00:13:18,881 --> 00:13:22,868 going to have it most n vertices and you're figuring out one of those vertices 211 00:13:22,868 --> 00:13:24,840 everytime you do a recursive call.