1 00:00:00,000 --> 00:00:03,423 We're now well positioned to state Johnson's algorithm in its full 2 00:00:03,423 --> 00:00:06,079 generality. The input as usual is a directed graph G. 3 00:00:06,079 --> 00:00:09,604 Each edge has a edge length C sub E, it could be positive or negative. 4 00:00:09,604 --> 00:00:12,670 The input graph G may or may not have a negative cost cycle. 5 00:00:12,670 --> 00:00:16,553 As usual, when we talk about solving a shortest path problem we mean that if 6 00:00:16,553 --> 00:00:20,538 there is no negative cost cycle, then we have no excuse. So we better correctly 7 00:00:20,538 --> 00:00:22,684 compute all of the desired shortest paths. 8 00:00:22,684 --> 00:00:24,880 In this case between all pairs of vertices. 9 00:00:24,880 --> 00:00:27,588 If there is a negative cost cycle, we're off the hook. 10 00:00:27,588 --> 00:00:29,990 We don't have to compute shortest paths, but we. 11 00:00:29,990 --> 00:00:35,120 need to correctly report that the graph does indeed have a negative cost cycle. 12 00:00:35,120 --> 00:00:38,018 Step one is the same hack that we used in the example. 13 00:00:38,018 --> 00:00:42,151 We want to make sure that there's a vertex from which we can reach everybody 14 00:00:42,151 --> 00:00:44,352 else. So let's just add a new one that by 15 00:00:44,352 --> 00:00:48,270 construction has that properties. So we add one new vertex to little s, we 16 00:00:48,270 --> 00:00:51,007 add N new edges. One from s to each of the original 17 00:00:51,007 --> 00:00:54,320 vertices and each of those new N edges has length zero. 18 00:00:54,320 --> 00:00:58,900 We're going to call this new, bigger graph g prime. 19 00:00:58,900 --> 00:01:02,857 The second step, just like in the example, is to run a shortest path 20 00:01:02,857 --> 00:01:05,811 computation using this new vertex S as the source. 21 00:01:05,811 --> 00:01:10,360 Since the graph G in general has negative etch cost, we have to resort to the 22 00:01:10,360 --> 00:01:14,800 Belmont Ford out rhythm to execute the shortest path computation. 23 00:01:14,800 --> 00:01:18,444 Recall that the Bellman-Ford Algorithm will do one of two things. 24 00:01:18,444 --> 00:01:22,818 Either it will correctly compute the shortest path distances that we're after, 25 00:01:22,818 --> 00:01:26,800 from the source vertex S to everybody else, or it will correctly report. 26 00:01:26,800 --> 00:01:31,033 That the graph it was fed, namely g prime, contains [SOUND] a negative cost 27 00:01:31,033 --> 00:01:33,664 cycle. Now, if g prime contains a negative cost 28 00:01:33,664 --> 00:01:36,410 cycle, that cycle has to be the original graph, g. 29 00:01:36,410 --> 00:01:40,357 Our, the new vertex, s, that we added, has no incoming arcs at all, so it 30 00:01:40,357 --> 00:01:44,304 certainly can't be on any cycle, [SOUND] so any negative cycle is the 31 00:01:44,304 --> 00:01:48,823 responsibility of the original graph, G. [SOUND] Therefore if Bellman-Ford finds 32 00:01:48,823 --> 00:01:53,399 us a negative cost cycle, we're free to just halt and correctly report that same 33 00:01:53,399 --> 00:01:57,053 result. So from here on out, we can safely assume 34 00:01:57,053 --> 00:02:01,301 that G and G prime have no negative cost cycle, and therefore that the 35 00:02:01,301 --> 00:02:05,440 Bellman-Ford algorithm did indeed correctly compute shortest path distances 36 00:02:05,440 --> 00:02:08,871 from S to everybody else. As in the example, we are going to use 37 00:02:08,871 --> 00:02:13,120 these shortest path distances, [SOUND] all of which are finite by construction. 38 00:02:13,120 --> 00:02:18,663 As our vertex weights, our P sub Vs. We then form the new edges lengths, the C 39 00:02:18,663 --> 00:02:23,477 primes, in the usual way. C prime of an edge E going from U to V is 40 00:02:23,477 --> 00:02:29,531 the original length CE plus the weight of the tail P sub U minus the weight of the 41 00:02:29,531 --> 00:02:34,123 head P sub V. In the example, we saw that the new edge 42 00:02:34,123 --> 00:02:39,019 length C prime are all non-negative. We will shortly prove that, that property 43 00:02:39,019 --> 00:02:42,453 holds in general. If you define your vertex weights in 44 00:02:42,453 --> 00:02:47,603 terms of shortest path distances from the new vertex S to everybody else in this 45 00:02:47,603 --> 00:02:52,817 augmented graph G Prime it is always the case that your new edge lengths would be 46 00:02:52,817 --> 00:02:56,187 non-negative. Assuming that for now, it makes sense to 47 00:02:56,187 --> 00:03:00,892 use Dijkstar's algorithm N times, once for each choice vertex to compute all 48 00:03:00,892 --> 00:03:06,160 pairs shortest paths in the graph G with the new edge length C prime. 49 00:03:06,160 --> 00:03:09,015 In a particular iteration of this four loop. 50 00:03:09,015 --> 00:03:12,585 Say, when we're using the vertex u as the source vertex. 51 00:03:12,585 --> 00:03:17,388 We're going to be computing n of the shortest path distances that we care 52 00:03:17,388 --> 00:03:19,919 about. From u to the various n possible 53 00:03:19,919 --> 00:03:23,100 destinations. And let's call those shortest paths 54 00:03:23,100 --> 00:03:26,540 computed by Dijkstra in this iteration d prime of u, v. 55 00:03:28,440 --> 00:03:31,407 So perhaps you're thinking that at this point we're done. 56 00:03:31,407 --> 00:03:33,594 Right? We transformed the edge links using 57 00:03:33,594 --> 00:03:37,447 re-weighting to make them non-negative and as we know once things are not 58 00:03:37,447 --> 00:03:39,738 negative end Dijjkstra and you're good to go. 59 00:03:39,738 --> 00:03:43,383 But there's one final piece of bookkeeping that we have to keep track 60 00:03:43,383 --> 00:03:45,570 of. So, the shortest path distances that we 61 00:03:45,570 --> 00:03:49,423 compute in step four, these D primes, these are the shortest path distances 62 00:03:49,423 --> 00:03:51,922 with respect to the modified costs, the C primes. 63 00:03:51,922 --> 00:03:56,243 And what we're responsible for outputting the shortest path distances with respect 64 00:03:56,243 --> 00:03:59,888 to the original links, the C's. But fortunately there's a very easy way 65 00:03:59,888 --> 00:04:02,440 to extract the true shortest path distances from. 66 00:04:02,440 --> 00:04:06,910 The D primes from the shortest path distances relative to the modified costs. 67 00:04:06,910 --> 00:04:11,594 We know that D primes are wrong, there computed with respect to the wrong costs. 68 00:04:11,594 --> 00:04:16,279 But we know exactly what they're off by. So D primes are off by exactly P sub U 69 00:04:16,279 --> 00:04:19,600 minus P sub V amount. So to go from the D primes back to 70 00:04:19,600 --> 00:04:24,344 shortest path distances that we really care about, we just need to subtract that 71 00:04:24,344 --> 00:04:30,076 term back off, and that's step five. [SOUND] That completes the description of 72 00:04:30,076 --> 00:04:34,923 Johnson's Algorithm which, in effect, is a reduction from the all pairs shortest 73 00:04:34,923 --> 00:04:40,076 path problem with general edge lengths to N plus one instances of the single source 74 00:04:40,076 --> 00:04:45,107 version of the problem, only one of which has general edge lengths, N of which have 75 00:04:45,107 --> 00:04:52,431 only non-negative edge lengths. [SOUND] Analyzing the running time of 76 00:04:52,431 --> 00:04:56,889 Johnson's algorithm is straight forward. Let's just look at the work done in each 77 00:04:56,889 --> 00:05:01,589 of the five steps. In step one, we just add one new vertex 78 00:05:01,589 --> 00:05:05,940 and n new edges, so that takes o of n time to accomplish. 79 00:05:07,000 --> 00:05:12,931 In step two we run the Bellman-Ford algorithm, so we know that takes O of M 80 00:05:12,931 --> 00:05:16,950 times N time. In step three, we have to compute the 81 00:05:16,950 --> 00:05:21,695 modified costs, but given the shortest path distances computed by Bellman Ford, 82 00:05:21,695 --> 00:05:24,920 that's constant time per edge or O of N time overall. 83 00:05:26,260 --> 00:05:29,908 In step four we went Dijkstra's out rhythm N times. 84 00:05:29,908 --> 00:05:33,780 And, the running time of one indication is N X login. 85 00:05:35,180 --> 00:05:41,929 In step five we do constant work for each choice of U and V, so O of N squared work 86 00:05:41,929 --> 00:05:47,514 overall. So you can see that step four dominates 87 00:05:47,514 --> 00:05:52,612 and the running time is equivalent to N invocations of Dijkstra's algorithm M 88 00:05:52,612 --> 00:05:57,320 times N times log N. As usual when discussing graph algorithms 89 00:05:57,320 --> 00:06:01,160 I am thinking about the graph as a least being weakly connected. 90 00:06:01,160 --> 00:06:04,880 I'm thinking of the number of edges M as being big omega of N. 91 00:06:06,200 --> 00:06:09,440 So why is this running time so cool? Well two reasons. 92 00:06:09,440 --> 00:06:13,841 The first reason is that for sparse graphs this solution blows away the 93 00:06:13,841 --> 00:06:18,243 previous algorithms that we had that could handle negative edge lengths. 94 00:06:18,243 --> 00:06:22,890 The two previous solutions that we knew, that you could use with graphs with 95 00:06:22,890 --> 00:06:27,169 negative edge lengths were either run Bellam Ford N times or used the 96 00:06:27,169 --> 00:06:31,143 Floyd-Warshall. And in sparse graphs where M is big O of 97 00:06:31,143 --> 00:06:34,872 N, both of those solutions run in cubic time or in cubed time. 98 00:06:34,872 --> 00:06:39,832 This solution for sparse graphs, when M is O of N is of, of N squared Times a log 99 00:06:39,832 --> 00:06:44,916 N factor, so it's way better than either using Bellman-Ford N times or using 100 00:06:44,916 --> 00:06:49,421 Floyd-Warshall. The second reason this running time is so 101 00:06:49,421 --> 00:06:53,386 cool is that it matches the running time we were getting already in the special 102 00:06:53,386 --> 00:06:57,202 case when edge links were non negative. so this is very different than how we 103 00:06:57,202 --> 00:07:01,267 were conditioned to think about the world when we talked about single source 104 00:07:01,267 --> 00:07:04,587 shortage path problems. Remember, in those problems, we have Dexter's 105 00:07:04,587 --> 00:07:08,651 algorithm which only handles non negative edge links but runs in near linear time 106 00:07:08,651 --> 00:07:12,765 and there's no algorithm known for single source shortest paths that's near linear 107 00:07:12,765 --> 00:07:16,730 that can handle negative edge links, the Bellman Ford algorithm certainly is not 108 00:07:16,730 --> 00:07:19,800 near linear running time. That's Big O of N times N. 109 00:07:19,800 --> 00:07:23,747 Johnson's Algorithm shows that while negative edge lengths are indeed an 110 00:07:23,747 --> 00:07:27,369 issue, they can be handled in one shot using just one invocation of 111 00:07:27,369 --> 00:07:30,019 Bellman-Ford. While the Bellman-Ford algorithm is 112 00:07:30,019 --> 00:07:34,453 indeed quite a bit slower than Dijkstra's algorithm, it's only roughly a factor of 113 00:07:34,453 --> 00:07:37,210 N slower. So one invocation of Bellman-Ford doesn't 114 00:07:37,210 --> 00:07:41,320 change the overall running time when we already have to do N invocations of 115 00:07:41,320 --> 00:07:45,808 Dijkstra's algorithm, even in the special case of the problem where all of the edge 116 00:07:45,808 --> 00:07:49,651 lengths are non-negative. So that is why for all pairs shortest 117 00:07:49,651 --> 00:07:53,582 paths we see a convergence in the performance of algorithms that solve the 118 00:07:53,582 --> 00:07:57,618 problem in general, and algorithms that only solve the problem in the special 119 00:07:57,618 --> 00:08:02,046 case of non-negative edge lengths. The missing piece to the correctness 120 00:08:02,046 --> 00:08:06,132 argument is understanding why in general the modified edge links, the C prime E's 121 00:08:06,132 --> 00:08:09,764 are guaranteed to be non-negative. We saw that they were non-negative in 122 00:08:09,764 --> 00:08:12,942 this specific example, but we have not yet proved it in general. 123 00:08:12,942 --> 00:08:16,372 We'll do that on the next slot. Assuming for the moment that, that is 124 00:08:16,372 --> 00:08:20,257 true, that the modified edge links are indeed non-negative, and therefore, when 125 00:08:20,257 --> 00:08:24,191 we invoke Dijkstra it will correctly compute shortest paths, we're pretty much 126 00:08:24,191 --> 00:08:26,461 done. In particular, recall that we had a quiz 127 00:08:26,461 --> 00:08:30,194 in the previous video where we analyzed the ramifications of re-weighting. 128 00:08:30,194 --> 00:08:33,725 And we saw that if you re-weight using particular vertex weights, some P sub Vs. 129 00:08:34,866 --> 00:08:39,274 Then, for a given choice of an origin u, and a given choice of a destination v. 130 00:08:39,274 --> 00:08:43,624 Every single uv path has its length changed by exactly the same amount, by a 131 00:08:43,624 --> 00:08:46,429 common amount. Namely, the difference between u as 132 00:08:46,429 --> 00:08:50,035 vertex weight p sub u. And the destination v as vertex weight, p 133 00:08:50,035 --> 00:08:52,610 sub v. So that means, when we invoke Dijkstra's 134 00:08:52,610 --> 00:08:56,159 algorithm in step four. Indeed, gets the shortest paths correct. 135 00:08:56,159 --> 00:08:58,563 The shortest path distances are incorrect. 136 00:08:58,563 --> 00:09:01,082 But we know exactly how much they're off by. 137 00:09:01,082 --> 00:09:04,860 They're off by Pu minus P sub v. And that is corrected for in step five. 138 00:09:04,860 --> 00:09:09,448 So that's why assuming correctness of Dykstra's algorithm Which in turn relies 139 00:09:09,448 --> 00:09:12,166 on non negativity of the modified edge links. 140 00:09:12,166 --> 00:09:16,636 The end result of Johnson's algorithm is indeed the correct shortest path 141 00:09:16,636 --> 00:09:26,153 distances. To finish the analysis of Johnson's 142 00:09:26,153 --> 00:09:29,878 algorithm all that remains is to prove the following claim. 143 00:09:29,878 --> 00:09:34,678 Which is that for every single edge of the graph, it's length after we do re 144 00:09:34,678 --> 00:09:39,075 weighting is non negative. So the proof in fact is not hard. 145 00:09:39,075 --> 00:09:43,653 It follows quite easily from properties of shortest path distances. 146 00:09:43,653 --> 00:09:48,060 So fix your favorite edge E, let's say going from U to V. 147 00:09:48,060 --> 00:09:52,825 The vertex weights are, by construction, just shortest path distances from the 148 00:09:52,825 --> 00:09:56,043 vertex little s. Well remember S is the extra source 149 00:09:56,043 --> 00:09:59,200 vertex that we added to the original input graph G. 150 00:10:03,860 --> 00:10:09,195 So by the way we constructed the graph G prime, there is at least one path from 151 00:10:09,195 --> 00:10:12,774 this auxiliary source vertex S to every other vertex. 152 00:10:12,774 --> 00:10:18,300 So there is some shortest path from S to U, let's call it capital P. 153 00:10:18,300 --> 00:10:24,680 By definition, the length of capital P has to be little p sub u. 154 00:10:24,680 --> 00:10:30,168 It's a simple matter to obtain from this path capital P, which goes from S to U. 155 00:10:30,168 --> 00:10:33,087 A path which goes from S all the way to V. 156 00:10:33,087 --> 00:10:36,700 Namely, just concatenates the edge UV as a final hop. 157 00:10:38,000 --> 00:10:42,176 The length of this path which goes from S to V is of course just the length 158 00:10:42,176 --> 00:10:46,682 incurred going from S to U, Which is just P sub U, plus the length of the final hop 159 00:10:46,682 --> 00:10:49,940 which is just the length of this edge, C sub U V. 160 00:10:49,940 --> 00:10:53,059 Now this is just some old path from S to V. 161 00:10:53,059 --> 00:10:57,412 The shortest path from S to V, can of course, only be shorter. 162 00:10:57,412 --> 00:11:02,853 And only piece of V, the vertex way to V, is by definition, the length of the 163 00:11:02,853 --> 00:11:08,035 shortest path from S to V. And now, we're good to go because the 164 00:11:08,035 --> 00:11:11,865 modified length of this edge C. That is C prime sub E is just the 165 00:11:11,865 --> 00:11:16,235 difference between the right hand side of this inequality and the left hand side. 166 00:11:16,235 --> 00:11:19,579 So that's why the difference is guaranteed to be non negative. 167 00:11:19,579 --> 00:11:22,816 Since this was an arbitrary edge it holds for all the edges. 168 00:11:22,816 --> 00:11:26,268 That completes the proof in the analysis of Johnson's algorithm.