1 00:00:00,000 --> 00:00:04,582 So why should we be content computing shortest paths from merely one source 2 00:00:04,582 --> 00:00:09,045 vertex to all possible destinations? What if we want to know shortest path 3 00:00:09,045 --> 00:00:12,520 distances from every vertex to every other vertex? 4 00:00:12,520 --> 00:00:17,078 The formal definition of the all pair shortest paths or APSP problem is as 5 00:00:17,078 --> 00:00:19,934 follows. You're given as usual, a directed graph 6 00:00:19,934 --> 00:00:24,493 G, with edges that have lengths C sub E. You can think, if you want, about the 7 00:00:24,493 --> 00:00:28,687 special case when all edges are not negative, but we're also going to be 8 00:00:28,687 --> 00:00:32,820 interested in the case when edges can have negative lengths as well. 9 00:00:34,440 --> 00:00:39,965 In contrast to the single source shortest path problem, there is no distinguished 10 00:00:39,965 --> 00:00:44,489 source vertex. And the goal of the problem is to compute 11 00:00:44,489 --> 00:00:49,737 for every pair of vertices u and v, the length of a shortest path starting at u 12 00:00:49,737 --> 00:00:53,948 and ending at v. Just as with the single source version of 13 00:00:53,948 --> 00:00:56,283 the problem, this isn't quite the full story. 14 00:00:56,283 --> 00:01:00,527 If the input graph g has a negative edge cycle, then either, depending on how you 15 00:01:00,527 --> 00:01:03,764 define shortest paths, the problem doesn't make sense or, it's 16 00:01:03,764 --> 00:01:07,212 computationally intractable. So, if there is a negative cost cycle, 17 00:01:07,212 --> 00:01:11,510 we're off the hook from having to compute shortest path distances, but we do need 18 00:01:11,510 --> 00:01:15,702 to correctly report in that case, that the graph contains a negative cost cycle. 19 00:01:15,702 --> 00:01:19,575 That's our excuse, our excuse, for not computing the correct shortest path 20 00:01:19,575 --> 00:01:23,989 lengths. So, you know what would make me really 21 00:01:23,989 --> 00:01:26,052 happy? If, when you see this problem, you 22 00:01:26,052 --> 00:01:30,230 thought to yourself, eh, don't we pretty much already have a rich enough toolbox 23 00:01:30,230 --> 00:01:32,610 to solve the all-pairs shortest path problem. 24 00:01:32,610 --> 00:01:36,471 If that's what you thought, that's a great thought and the answer, in many 25 00:01:36,471 --> 00:01:39,062 senses, is yes. So let's explore that idea, make it 26 00:01:39,062 --> 00:01:41,390 precise. In the following quiz, I'm going to ask 27 00:01:41,390 --> 00:01:45,303 you, suppose I gave you, as a black box, a subroutine that solves the single 28 00:01:45,303 --> 00:01:48,001 source shortest path problem correctly and quickly. 29 00:01:48,001 --> 00:01:50,910 How many times would you need to invoke that black box? 30 00:01:50,910 --> 00:01:56,040 That subroutine to correctly solve the all pairs shortest path problem. 31 00:02:01,440 --> 00:02:04,668 So, the correct answer is C. You need N indications of the single 32 00:02:04,668 --> 00:02:08,552 source shortest path sub-routine, or N is the number of vertices in the input 33 00:02:08,552 --> 00:02:09,057 graph. Why? 34 00:02:09,057 --> 00:02:12,941 Well if you designate an arbitrary vertex as a source for text S and run the 35 00:02:12,941 --> 00:02:16,926 provided sub-routine, it will compute for you shortest path distances from that 36 00:02:16,926 --> 00:02:20,659 choice of S to all the destinations. So that computes for you N, a, shortest 37 00:02:20,659 --> 00:02:23,837 path distances out of the N square that you're responsible for. 38 00:02:23,837 --> 00:02:27,873 All the shortest path distances that has this particular vertex S as the origin. 39 00:02:27,873 --> 00:02:30,799 So there's N different choices out of the possible origin. 40 00:02:30,799 --> 00:02:34,632 So, you just interate out of all those choices and hopefully provide the out 41 00:02:34,632 --> 00:02:37,180 rhythm for once. Each and boom, you've got the N squared 42 00:02:37,180 --> 00:02:39,500 shortest path distances that you're responsible for. 43 00:02:40,600 --> 00:02:42,821 So, should we be happy with this reduction? 44 00:02:42,821 --> 00:02:47,106 Should we be happy with this algorithm that simply runs a single source shortest 45 00:02:47,106 --> 00:02:49,856 path algorithm n times? Or do we expect to do better? 46 00:02:49,856 --> 00:02:53,242 Well, the answer's going to depend. It's going to depend on two factors. 47 00:02:53,242 --> 00:02:56,838 First of all, does the input graph have only non negative edge costs? 48 00:02:56,838 --> 00:02:59,801 Or does it more generally also have negative edge costs? 49 00:02:59,801 --> 00:03:03,239 The second thing we want to look at is whether the graph is sparse. 50 00:03:03,239 --> 00:03:06,148 Meaning m, the number of edges is relatively close to n. 51 00:03:06,148 --> 00:03:08,793 Or is it dense, meaning m is relatively close to n^2? 52 00:03:08,793 --> 00:03:12,020 So let's start with the case of just non negative edge costs. 53 00:03:13,380 --> 00:03:18,478 The reason it matters whether or not the edge costs are all non negative or not is 54 00:03:18,478 --> 00:03:22,410 it governs which single source shortest path team we get to use. 55 00:03:22,410 --> 00:03:26,833 So if, the happy case, all edge costs are not negative, then we get to use 56 00:03:26,833 --> 00:03:31,502 Dijkstra's algorithm as our work horse. And remember Dijkstra's algorithm is 57 00:03:31,502 --> 00:03:35,003 blazingly fast. Our heap based implementation of it Ray M 58 00:03:35,003 --> 00:03:38,382 time M log N. So if you run that N times you're running 59 00:03:38,382 --> 00:03:45,120 time is naturally N times M times log N. So in the sparse case this is going to be 60 00:03:45,120 --> 00:03:49,080 N squared log N. In the dense this is going to be N cubed 61 00:03:49,080 --> 00:03:52,116 log N. [SOUND] So for sparse graphs, this 62 00:03:52,116 --> 00:03:55,317 frankly is pretty awesome. You're not going to really do much 63 00:03:55,317 --> 00:03:59,457 better, than running Dijkstra n times, once for each choice of source, of the 64 00:03:59,457 --> 00:04:02,216 source vertex. The reason is, we're responsible for 65 00:04:02,216 --> 00:04:06,356 outputting n squared values, the shortest path distance for each pair uv of 66 00:04:06,356 --> 00:04:08,894 vertices. And so here, the running time is just 67 00:04:08,894 --> 00:04:11,378 that n squared, times an extra log, log factor. 68 00:04:11,378 --> 00:04:15,680 [SOUND] The situation for dense graphs, however, is much murkier. 69 00:04:15,680 --> 00:04:19,290 And it is an open question to this day whether there are algorithms 70 00:04:19,290 --> 00:04:23,537 fundamentally faster than cubic time for the all pair shortest paths problem in 71 00:04:23,537 --> 00:04:26,457 dense graphs. If you wanted to try to convince somebody 72 00:04:26,457 --> 00:04:30,545 that maybe you couldn't do better than cubic time, you might argue as follows. 73 00:04:30,545 --> 00:04:34,740 There's a quadratic number of shortest path distances that have to be computed. 74 00:04:34,740 --> 00:04:38,562 And for a given pair, u and v, the shortest path might well have a linear 75 00:04:38,562 --> 00:04:41,429 number of edges in it. So, surely, you can't compute the 76 00:04:41,429 --> 00:04:44,350 shortest path between one pair better than linear time. 77 00:04:44,350 --> 00:04:48,350 So then the quadratic number is going to have to be cubic time. 78 00:04:48,350 --> 00:04:50,757 However, I want to be clear. This is not a proof. 79 00:04:50,757 --> 00:04:53,859 This is just a wishy washy argument. Why is it not a proof? 80 00:04:53,859 --> 00:04:57,550 Well, for all we know, we can do some amount of work which is relevant 81 00:04:57,550 --> 00:05:00,545 simultaneously for lots of these shortest path problems. 82 00:05:00,545 --> 00:05:04,236 And you don't actually have to spend linear on average time for each. 83 00:05:04,236 --> 00:05:08,034 As a tale of inspiration, let me remind you about matrix multiplication. 84 00:05:08,034 --> 00:05:12,260 If you write down the definition of what it means to multiply two matrices, you 85 00:05:12,260 --> 00:05:16,432 look at the definition and it just seems like it's an obviously cubic problem. 86 00:05:16,432 --> 00:05:20,230 It just seems like by definition, you have to do a cubic amount of work. 87 00:05:20,230 --> 00:05:22,646 [SOUND] Yet, that intuition is totally wrong. 88 00:05:22,646 --> 00:05:26,819 Beginning with Strassen, and then many following algorithms, we now know that 89 00:05:26,819 --> 00:05:30,828 there are algorithms for matrix multiplication, fundamentally better than 90 00:05:30,828 --> 00:05:34,562 the naive, cubic time algorithm. If you have a, nontrivial approach to 91 00:05:34,562 --> 00:05:38,626 decomposing a problem, you can eliminate some of the redundant work, and do 92 00:05:38,626 --> 00:05:40,877 better, than the straightforward solution. 93 00:05:40,877 --> 00:05:45,270 Is a Strassen-like improvement possible for the all pair shortest paths problem? 94 00:05:45,270 --> 00:05:51,378 [SOUND] Nobody knows. Now let's discuss the general case in 95 00:05:51,378 --> 00:05:54,598 quick graphs that are allowed to have negative edge lengths. 96 00:05:54,598 --> 00:05:58,944 So in this case we cannot use Dikstra's algorithm as our workhorse, as our single 97 00:05:58,944 --> 00:06:02,700 source shortest path subroutine. We have to resort to the Bellman-Ford 98 00:06:02,700 --> 00:06:07,207 algorithm instead because that's the only one of the two that accommodates negative 99 00:06:07,207 --> 00:06:09,890 cost edges. Remember the Bellman-Ford algorithm is 100 00:06:09,890 --> 00:06:14,022 slower than Dikstras algorithm, the running time down that we proved was O of 101 00:06:14,022 --> 00:06:16,704 M times N. If we run that N times we get a running 102 00:06:16,704 --> 00:06:22,218 time of M times M squared. How good is the running time of N squared 103 00:06:22,218 --> 00:06:24,443 M? Well, if the graph is sparse, if M is 104 00:06:24,443 --> 00:06:28,834 theta of N, then this is cubic in N. And if the graph is dense, M is theta of 105 00:06:28,834 --> 00:06:33,167 N squared, we're now seeing our first ever for this course, quartic running 106 00:06:33,167 --> 00:06:36,535 time. Hey and I hope that you're not really 107 00:06:36,535 --> 00:06:40,400 especially happy with the cubic running time down for the sparse graph case, but 108 00:06:40,400 --> 00:06:44,120 now when we're talking about quartic running time, now this just really seems 109 00:06:44,120 --> 00:06:46,632 exorbitant. And so hopefully you're thinking there's 110 00:06:46,632 --> 00:06:50,207 gotta be a better approach to this problem than just running Bellman-Ford 111 00:06:50,207 --> 00:06:53,444 N-times in the dense graph case. Indeed, there is: the Floyd-Warshall 112 00:06:53,444 --> 00:06:55,860 algorithm, we'll start talking about it next video.