1 00:00:00,000 --> 00:00:03,800 In this next sequence of videos, we're going to revisit the single source 2 00:00:03,800 --> 00:00:07,079 shortest path problem. This is a problem that we already solved 3 00:00:07,079 --> 00:00:10,359 using Dijkstra's greedy algorithm. Now let's see what the dynamic 4 00:00:10,359 --> 00:00:13,222 programming paradigm can do for us for the same problem. 5 00:00:13,222 --> 00:00:16,970 Let me just quickly remind you the definition of the problem, what's the 6 00:00:16,970 --> 00:00:19,946 input, what's the output. We're given a graph. 7 00:00:19,946 --> 00:00:24,160 And when we talk about shortest path, we're going to be discussing only 8 00:00:24,160 --> 00:00:27,245 directed graphs. Each edge of the graph has a length, 9 00:00:27,245 --> 00:00:31,720 which we're going to denote by c-sub-e. And one vertex which we'll denote by a 10 00:00:31,720 --> 00:00:34,324 little less is designated as the source vertex. 11 00:00:34,324 --> 00:00:37,038 We're going to assume that the graphs are simple. 12 00:00:37,038 --> 00:00:41,304 That is, there are no parallel edges. The reasoning is the same as the minimum 13 00:00:41,304 --> 00:00:44,572 spanning tree problem if you had a bunch of parallel edges. 14 00:00:44,572 --> 00:00:48,838 Since we only care about the shortest path, you may as well throw away all of 15 00:00:48,838 --> 00:00:52,716 the copies of an edge except for the one that has the smallest length. 16 00:00:52,716 --> 00:00:57,148 The responsibility of an algorithm for this problem is to compute the length of 17 00:00:57,148 --> 00:01:01,940 a shortest path from this source vertex S to every other possible destination V. 18 00:01:01,940 --> 00:01:06,147 And always, when we talk about the link of a path, we mean the sum of the edge 19 00:01:06,147 --> 00:01:08,770 costs, of all of the edges that are in that path. 20 00:01:08,770 --> 00:01:13,032 For example, if the cost of every edge was one, then we'd just be talking about 21 00:01:13,032 --> 00:01:17,020 the hob count, and that's a problem that's solved using breath per search. 22 00:01:17,020 --> 00:01:21,173 But in general in this single source shortest path problem, we're interested 23 00:01:21,173 --> 00:01:25,260 in edges, that has possibly wildly different links from each other. 24 00:01:25,260 --> 00:01:30,315 So let's now review our existing solution for the problem Dijkstra's algorithm. 25 00:01:30,315 --> 00:01:34,502 Review its pros and its cons. The Dijkstra's algorithm is a great 26 00:01:34,502 --> 00:01:37,201 algorithm. If you have a graph and it fits in your 27 00:01:37,201 --> 00:01:41,519 computer's main memory and all the edge costs are non negative, if you implement 28 00:01:41,519 --> 00:01:45,512 Dijkstra's algorithm using heaps, you will get a blazingly fast and always 29 00:01:45,512 --> 00:01:49,882 correct shortest path algorithm. Part one of this course we explained an 30 00:01:49,882 --> 00:01:53,884 implementation using heaps that runs in Big O of M times login time. 31 00:01:53,884 --> 00:01:57,615 Where as usual M is the number edges and N is the number of vertices. 32 00:01:57,615 --> 00:02:01,724 And this implementation is almost identical to the one we discussed earlier 33 00:02:01,724 --> 00:02:05,942 in this course for prims algorithm computing the minimum of a spanning tree. 34 00:02:05,942 --> 00:02:09,781 It turns out you can get an even better acetonic running time, at least 35 00:02:09,781 --> 00:02:13,872 theoretically, a running time of M. Plus and login if you use a more exotic 36 00:02:13,872 --> 00:02:18,320 type of data structure but let's for now just think of this as the line in the 37 00:02:18,320 --> 00:02:22,768 sand big o of m login using dice wishin algorithm on a graph with non negative 38 00:02:22,768 --> 00:02:26,316 edge lengths. So given what a great algorithm 39 00:02:26,316 --> 00:02:30,207 Dijkstra's algorithm is, on what basis could we reject it and study any other 40 00:02:30,207 --> 00:02:33,087 shortest path algorithm? Well, there's two drawbacks we've 41 00:02:33,087 --> 00:02:35,260 mentioned before, let me reiterate them now. 42 00:02:36,360 --> 00:02:40,641 So first of all if you're working with a graph where some of the edge costs can be 43 00:02:40,641 --> 00:02:43,736 negative, then the output of Dijkstra's algorithm need not be correct. 44 00:02:43,736 --> 00:02:47,038 The correctness relies on the non-negative edge cost assumption. 45 00:02:47,038 --> 00:02:51,061 We saw concrete examples of this both back in part one of the course, but also 46 00:02:51,061 --> 00:02:55,240 in this course when we first started talking about greedy algorithms and we 47 00:02:55,240 --> 00:02:57,510 discussed to their ubiquitous incorrectness. 48 00:02:57,510 --> 00:03:01,205 Now frankly, for many of the applications of shortest path algorithms you're never 49 00:03:01,205 --> 00:03:04,720 going to run into negative edge lengths. If you are implementing, for example, a 50 00:03:04,720 --> 00:03:08,326 program that computes driving directions, whether you're doing it in miles or in 51 00:03:08,326 --> 00:03:11,661 time, you're not going to have negative length edges, at least until we get 52 00:03:11,661 --> 00:03:14,580 finally get around to inventing those time travel machines. 53 00:03:14,580 --> 00:03:18,671 But not all applications of the shortest path problem are so literal and involve 54 00:03:18,671 --> 00:03:22,359 literally computing some path in space from some point A to some point B. 55 00:03:22,359 --> 00:03:26,198 More abstractly, the problem is just helping you find an optimal sequence of 56 00:03:26,198 --> 00:03:28,573 decisions. Imagine you were managing a bunch of 57 00:03:28,573 --> 00:03:32,513 financial assets, for example, and you were modeling a single transaction as an 58 00:03:32,513 --> 00:03:36,251 edge in a network that takes you from one particular inventory to another. 59 00:03:36,251 --> 00:03:40,141 When you sell stuff, that might generate positive revenue and correspond to a 60 00:03:40,141 --> 00:03:44,031 positive edge length, but when you buy stuff then, of course, you have to spend 61 00:03:44,031 --> 00:03:47,640 money and that can correspond to a negative edge length. 62 00:03:47,640 --> 00:03:51,898 So the second drawback which we mentioned in the intro video for this course, is 63 00:03:51,898 --> 00:03:54,613 that dijkstra's algorithm seems highly centralized. 64 00:03:54,613 --> 00:03:58,925 Now, that's not a problem if you just are destroying the entire graph in the main 65 00:03:58,925 --> 00:04:02,917 memory of one machine, but if you're talking about routing in the interenet. 66 00:04:02,917 --> 00:04:07,016 Well it's totally impractical for a router to have a up to date complete map 67 00:04:07,016 --> 00:04:11,381 of the entire internet to compute routes locally and so that motivates looking at 68 00:04:11,381 --> 00:04:15,374 a different shortest path algorithm, which is better suited for distributed 69 00:04:15,374 --> 00:04:19,901 routing. So we're going to be able to address both 70 00:04:19,901 --> 00:04:24,708 of these drawbacks in one fell swoop via the Bellman-Ford algorithm, which will be 71 00:04:24,708 --> 00:04:29,740 yet another instantiation of the dynamic programing algorithm design paradigm. 72 00:04:29,740 --> 00:04:33,697 This Bellman Ford algorithm, despite predating the earliest version of the 73 00:04:33,697 --> 00:04:37,762 ARPAnet by a good ten years, nevertheless does form the basis for modern day 74 00:04:37,762 --> 00:04:41,292 internet routing protocols. Of course there's a lot of engineering 75 00:04:41,292 --> 00:04:45,036 steps that you need to go from the abstract Bellman Ford algorithm to 76 00:04:45,036 --> 00:04:48,940 practical solution internet routing. We'll discuss that a little bit in a 77 00:04:48,940 --> 00:04:52,150 separate video, but this really is where it all gets started. 78 00:04:52,150 --> 00:04:56,452 So before we start developing the Bellman Ford algorithm, we need to take care of 79 00:04:56,452 --> 00:04:59,746 some subtle preliminaries. We need to be clear about how we're 80 00:04:59,746 --> 00:05:04,049 defining shortest paths in the presence of negative edge costs and in particular 81 00:05:04,049 --> 00:05:07,927 in the presence of negative edge, negative cost cycles, that is a directed 82 00:05:07,927 --> 00:05:11,660 cycle of edges where the sum of the edge costs is less than zero. 83 00:05:11,660 --> 00:05:16,199 You can think for example about this green cartoon I've drawn off on the right 84 00:05:16,199 --> 00:05:20,739 where somewhere embedded in this graph is a directed cycle that has four edges. 85 00:05:20,739 --> 00:05:25,106 Some of the edges in the cycle have negative cost, some have positive but on 86 00:05:25,106 --> 00:05:29,645 balance the cycle has negative overall cost, cost minus two if you traverse all 87 00:05:29,645 --> 00:05:33,600 four of the edges. So let's think about how we should define 88 00:05:33,600 --> 00:05:38,840 the shortest path from the source vertex S to some destination V in a graph like 89 00:05:38,840 --> 00:05:41,584 this. Do, in particular, do we allow cycles in 90 00:05:41,584 --> 00:05:44,641 the path or not. So first let's think through the 91 00:05:44,641 --> 00:05:48,010 ramifications of allowing the paths to include cycles. 92 00:05:48,010 --> 00:05:50,249 So this proposal actually doesn't make sense. 93 00:05:50,249 --> 00:05:53,931 In that generally there will be no shortest path from S to V if you allow 94 00:05:53,931 --> 00:05:56,568 cycle traversals. The reason being that if you have a 95 00:05:56,568 --> 00:06:00,499 negative cycle like this one of overall cost minus two in the screen graph, and 96 00:06:00,499 --> 00:06:04,529 you can actually reach it from the source S, then for every path you can actually 97 00:06:04,529 --> 00:06:08,560 find another path which is even shorter. You traverse the directed cycle one more 98 00:06:08,560 --> 00:06:10,600 time. The path overall path link drops by 99 00:06:10,600 --> 00:06:14,431 another minus two, and there's nothing from stopping you from doing this over 100 00:06:14,431 --> 00:06:17,716 and over and over again. So either the shortest path you can think 101 00:06:17,716 --> 00:06:21,505 of it as being undefined. Or you can think of it as being sort of, 102 00:06:21,505 --> 00:06:26,142 minus infinity in the limit. So if permitting our path to have cycles 103 00:06:26,142 --> 00:06:30,958 didn't work, why not we explore the option where we forbid cycles in our 104 00:06:30,958 --> 00:06:33,709 paths? So this version of the problem is 105 00:06:33,709 --> 00:06:36,811 perfectly well defined. It's a totally sensible computational 106 00:06:36,811 --> 00:06:38,997 problem, which you might well want to solve. 107 00:06:38,997 --> 00:06:42,862 The issue here is much more subtle. The issue is that this problem is what's 108 00:06:42,862 --> 00:06:46,575 called np complete, so that's something we'll discuss much more next week. 109 00:06:46,575 --> 00:06:49,321 But the bottom line is these are intractable problems. 110 00:06:49,321 --> 00:06:52,779 There are no known computational efficient, no known polynomial-time 111 00:06:52,779 --> 00:06:56,389 algorithms for np complete problems. And this, unfortunately, is one such 112 00:06:56,389 --> 00:06:58,932 problem. Computing shortest cycle-through paths in 113 00:06:58,932 --> 00:07:04,128 the presence of negative cycles. So a bit more precisely, if you came up 114 00:07:04,128 --> 00:07:08,082 with a guaranteed correct and guaranteed polynomial time algorithm, that was 115 00:07:08,082 --> 00:07:12,192 computed shortest path and presence of negative cycles, the, a consequence would 116 00:07:12,192 --> 00:07:15,522 be what's called P = NP. And that's something we'll discuss a bit 117 00:07:15,522 --> 00:07:19,164 more formally in a later video. But, certainly if you came up with such 118 00:07:19,164 --> 00:07:22,546 an algorithm you should report immediately to the Clay Institute. 119 00:07:22,546 --> 00:07:26,500 They would have a $1,000,000 prize awaiting for you for such an algorithm. 120 00:07:27,960 --> 00:07:31,787 So for those of you that are already familiar with NP completeness, it would 121 00:07:31,787 --> 00:07:34,707 be an easy exercise to prove that this problem is NP hard. 122 00:07:34,707 --> 00:07:38,300 It would just be a reduction from the Hamiltonian path problem. 123 00:07:38,300 --> 00:07:41,519 So it seems that we are stuck between a rock and a hard place. 124 00:07:41,519 --> 00:07:44,947 If we allow cycles in our paths, we don't get a meaningful problem. 125 00:07:44,947 --> 00:07:49,154 We get something that doesn't make sense. If we exclude cycles, we get a perfectly 126 00:07:49,154 --> 00:07:52,530 meaningful, but unfortunately computationally intractable problem. 127 00:07:52,530 --> 00:07:56,405 So here's how we're going to proceed, we're going to focus for now, just on 128 00:07:56,405 --> 00:08:01,021 graphs that do not have negative cycles. We will of course allow individual edges 129 00:08:01,021 --> 00:08:05,068 to be negative, but we're going to insist for the moment that every single 130 00:08:05,068 --> 00:08:08,886 directive cycle of the input graph has overall non negative length. 131 00:08:08,886 --> 00:08:12,534 So we can have some positive edge cost, some negative edge costs. 132 00:08:12,534 --> 00:08:18,857 But overall it has to be non negative. Now I don't blame you if this assumption 133 00:08:18,857 --> 00:08:22,858 bothers you, but the good news is, as we'll see, the Bellman-Ford Algorithm 134 00:08:22,858 --> 00:08:25,969 effortlessly checks whether or not this condition holds. 135 00:08:25,969 --> 00:08:30,080 It effortlessly detects a negative cycle in the input graph if one exists. 136 00:08:30,080 --> 00:08:34,192 So the version of the shortest path problem that Bellman Ford Algorithm is 137 00:08:34,192 --> 00:08:37,970 going to solve will be the following. Given an input graph which has. 138 00:08:37,970 --> 00:08:40,833 Negative edge costs. It may or may not have a negative cycle. 139 00:08:40,833 --> 00:08:44,699 The Bellman Ford algorithm will either correctly compute shortest paths from the 140 00:08:44,699 --> 00:08:48,421 source to all of the destinations just like you wanted, or it will punt, but it 141 00:08:48,421 --> 00:08:50,665 will offer you a good excuse for why it punted. 142 00:08:50,665 --> 00:08:54,339 It will show you a negative cycle in the input graph and of course computing 143 00:08:54,339 --> 00:08:57,823 shortest path is intractable in the presence of a negative cycle so with 144 00:08:57,823 --> 00:09:00,973 Bellman Ford you have to sort of let it off the hook in that case. 145 00:09:00,973 --> 00:09:03,169 Okay? So it will give it an input graph either 146 00:09:03,169 --> 00:09:06,939 it will show you a negative cycle or it will give you all of the shortest path 147 00:09:06,939 --> 00:09:09,135 distances. That's the guarantee we're going to 148 00:09:09,135 --> 00:09:13,738 strive for. So I'm going to end this video with a 149 00:09:13,738 --> 00:09:18,745 quiz helping you understand why this hypothesis of no negative cycles might be 150 00:09:18,745 --> 00:09:22,865 useful in an algorithm. So for now I just want you to think about 151 00:09:22,865 --> 00:09:27,049 suppose I promised you that an input graph had no negative cycles. 152 00:09:27,049 --> 00:09:31,929 And the question is how many hops, how many edges, are sufficient to guarantee 153 00:09:31,929 --> 00:09:36,620 that you found the shortest path between S and some given destination phi. 154 00:09:40,360 --> 00:09:44,933 So the correct answer is A and this is one of the main reasons the no negative 155 00:09:44,933 --> 00:09:50,027 cycle hypothesis is useful it gives you control over how many edges are necessary 156 00:09:50,027 --> 00:09:52,575 to ensure that you've got the shortest path. 157 00:09:52,575 --> 00:09:57,032 So specifically suppose you had a path between some S and some V that had at 158 00:09:57,032 --> 00:09:58,020 least. N edges. 159 00:09:58,020 --> 00:10:02,566 Well if we have at least ten edges it means the path visits at least, N+11 160 00:10:02,566 --> 00:10:05,703 vertices. There's only N vertices, so if you visit 161 00:10:05,703 --> 00:10:09,225 at least, N+11, that means you visit one vertex twice, say X. 162 00:10:09,225 --> 00:10:14,027 So, that means you have a cycle inside your path that goes from X back to X 163 00:10:14,027 --> 00:10:16,781 again. Now, if you rip out this cycle, if you 164 00:10:16,781 --> 00:10:21,519 just delete those edges you get another path from S to V and because, this 165 00:10:21,519 --> 00:10:24,848 directed cycle as they all are, must be non negative. 166 00:10:24,848 --> 00:10:29,843 The total length of some of the edge cost has only gone down, by removing this 167 00:10:29,843 --> 00:10:34,676 cycle, so you show me, Path from s to the u with the least end edges I will show 168 00:10:34,676 --> 00:10:39,279 you a path with fewer edges and that is at least as short could only be short so 169 00:10:39,279 --> 00:10:43,940 that shows you that the shortest path or a shortest path has our most n minus one 170 00:10:43,940 --> 00:10:46,100 edges which is the answer to the quiz.