1 00:00:00,000 --> 00:00:04,084 We've arrived at another one of computer science's greatest hits, namely 2 00:00:04,084 --> 00:00:07,936 Dijkstra's shortest path algorithm. So let me tell you about the problem. 3 00:00:07,936 --> 00:00:10,510 It's a problem called single-source shortest paths. 4 00:00:10,510 --> 00:00:14,493 Basically what we want to do is compute something like driving directions. 5 00:00:14,493 --> 00:00:18,800 So we're given as input a graph, in this lecture I'm going to work with directed 6 00:00:18,800 --> 00:00:21,276 graphs. Although the same algorithm would work 7 00:00:21,276 --> 00:00:23,645 for undirected graphs with cosmetic changes. 8 00:00:23,645 --> 00:00:28,005 As usual we'll use N to denote the number of edges and N to denote the number of 9 00:00:28,005 --> 00:00:30,484 vertices. The input also includes two extra 10 00:00:30,484 --> 00:00:33,240 ingredients. First of all for each edge E, we're 11 00:00:33,240 --> 00:00:37,815 giving as input a non negative length which also denotes by else of V and the 12 00:00:37,815 --> 00:00:41,979 context of a driving direction application else of V could also denote 13 00:00:41,979 --> 00:00:45,322 to the mileage. How long, this particular road is or it 14 00:00:45,322 --> 00:00:48,900 could also denote, the expected travel time along the edge. 15 00:00:48,900 --> 00:00:52,940 The second ingredient is a vertex from which we, are looking for paths. 16 00:00:52,940 --> 00:00:57,269 This is exactly the same as we had in breadth first search and depth first 17 00:00:57,269 --> 00:00:59,751 search. We have an originating vertex, which 18 00:00:59,751 --> 00:01:04,333 we'll call here, the source. Our responsibility then is to, given this 19 00:01:04,333 --> 00:01:08,388 input, compute for every other vertex V, in this network. 20 00:01:08,388 --> 00:01:14,066 The length of the shortest path from the source vertex S, to that destination 21 00:01:14,066 --> 00:01:16,789 vertex, V. And so just to be clear, what is the 22 00:01:16,789 --> 00:01:19,534 length of a path that has, say, three edges in it? 23 00:01:19,534 --> 00:01:23,882 Well, it's just the sum of the length of the first edge in the path plus the 24 00:01:23,882 --> 00:01:28,401 length of the second edge in the path plus the length of the third edge in the 25 00:01:28,401 --> 00:01:31,089 path. So if you had a path like this with three 26 00:01:31,089 --> 00:01:35,551 edges and lengths one, two and three, then the length of the path would just be 27 00:01:35,551 --> 00:01:38,095 six. And then we define the short SV path in 28 00:01:38,095 --> 00:01:41,336 the natural way. So, amongst all the path directed from S 29 00:01:41,336 --> 00:01:45,734 to V, each one has it's own respected path lengths, and then the minimum over 30 00:01:45,734 --> 00:01:49,496 all SV paths is the shortest path distance in the graph G. 31 00:01:49,496 --> 00:01:54,242 So, I am going to make two assumption for these lectures one is really just for 32 00:01:54,242 --> 00:01:56,846 convenience the other is really important. 33 00:01:56,846 --> 00:02:00,261 The other assumption without which Dijkstra's algorithm is not correct, as 34 00:02:00,261 --> 00:02:02,617 we'll see. So, for convenience, we'll assume that 35 00:02:02,617 --> 00:02:05,931 there is a directed path from S to every other vertex V in the graph. 36 00:02:05,931 --> 00:02:09,438 Otherwise, the shortest path distance is something we'd define to be plus 37 00:02:09,438 --> 00:02:11,455 infinity. And the reason this is not a big 38 00:02:11,455 --> 00:02:15,106 assumption is, if you think about it, you could detect which vertices are not 39 00:02:15,106 --> 00:02:18,613 reachable from S just in a preprocessing step using say, breadth-first or 40 00:02:18,613 --> 00:02:21,495 depth-first search. And then you could delete the irrelevant 41 00:02:21,495 --> 00:02:25,404 part of the graph and run Dijkstra's algortihm as we'll describe it on what 42 00:02:25,404 --> 00:02:27,905 remains. Alternatively, Dijkstra's Algortihm will 43 00:02:27,905 --> 00:02:32,418 quite naturally figure out which vertices there are paths to from S, and which ones 44 00:02:32,418 --> 00:02:34,756 there are not. So this won't really come up. 45 00:02:34,756 --> 00:02:39,051 So, to keep it simple, just think about we have an input graph, where you can get 46 00:02:39,051 --> 00:02:41,281 from S to V, for every different vertex V. 47 00:02:41,281 --> 00:02:45,685 And the challenge then is to amongst all the ways to get from S to V, what is the 48 00:02:45,685 --> 00:02:49,191 shortest way to do it. So the second assumption already appears 49 00:02:49,191 --> 00:02:53,380 in the problem statement, but I want to reiterate it just so it's really clear. 50 00:02:54,420 --> 00:02:58,994 When we analyze Dijkstra's algorithm we always focus on graphs where every length 51 00:02:58,994 --> 00:03:02,063 is non negative. No negative edge links are allowed and 52 00:03:02,063 --> 00:03:05,280 we'll see why a little bit later in the, in the video. 53 00:03:05,280 --> 00:03:08,722 Now in the context of a driving directions application, it's natural to 54 00:03:08,722 --> 00:03:12,504 ask the question, why would you ever care about negative edge lengths?" Until we 55 00:03:12,504 --> 00:03:16,286 invent a time machine, it doesn't seem like negative edge lengths are going to 56 00:03:16,286 --> 00:03:20,020 be relevant when you're computing literal paths, through literal networks, but 57 00:03:20,020 --> 00:03:24,457 again remember that paths can be thought of as more abstractly as a just sequence 58 00:03:24,457 --> 00:03:26,862 of decisions. And some of the most powerful 59 00:03:26,862 --> 00:03:30,570 applications of shortest paths are. Coming up with optimal ways such 60 00:03:30,570 --> 00:03:33,223 sequences. So, for example, maybe you're engaging in 61 00:03:33,223 --> 00:03:37,520 financial transactions and you have the option of both buying and selling assets 62 00:03:37,520 --> 00:03:40,543 at different times. If you sell, then you get some kind of 63 00:03:40,543 --> 00:03:43,567 profit and that would correspond to a negative edge link. 64 00:03:43,567 --> 00:03:47,440 So there are quite interesting applications in which negative edge links 65 00:03:47,440 --> 00:03:49,794 are relevant. If you are dealing with such an 66 00:03:49,794 --> 00:03:52,916 application, Dykstra's Algorithm is not the algorithm to use. 67 00:03:52,916 --> 00:03:55,205 There's a different shortest path algorithm. 68 00:03:55,205 --> 00:03:58,899 A couple other ones but the most well known one is called Bellman-Ford. 69 00:03:58,899 --> 00:04:02,801 That's something based on dynamic programming, which we may well cover in a 70 00:04:02,801 --> 00:04:03,789 sequel course. Okay? 71 00:04:03,789 --> 00:04:07,327 So, for Dijkstra's Algorithm, we always focus on graphs that have only 72 00:04:07,327 --> 00:04:12,516 non-negative edge lengths. So with the next quiz I just want to make 73 00:04:12,516 --> 00:04:16,106 sure that you understand the single shore shortest path problem. 74 00:04:16,106 --> 00:04:20,481 Here let me draw for you here a simple four note network and ask you for what 75 00:04:20,481 --> 00:04:24,857 are the four shortest path lengths so from the source vertex X to each of the 76 00:04:24,857 --> 00:04:27,328 verticies in the network. Alright, 77 00:04:27,328 --> 00:04:30,760 so the answer to this quiz is the final option 0136. 78 00:04:30,760 --> 00:04:33,005 to see why that's true. Well, 79 00:04:33,005 --> 00:04:37,956 All of the options had zero as the shortest path distance from S to itself 80 00:04:37,956 --> 00:04:43,237 so that just seemed kind of obvious. So the empty path will get you from S to 81 00:04:43,237 --> 00:04:47,924 itself and have zero length. Now, suppose you wanted to get from S to 82 00:04:47,924 --> 00:04:50,762 V. Well, there's actually only one way to do 83 00:04:50,762 --> 00:04:53,667 that. You have to go along this one hop path. 84 00:04:53,667 --> 00:04:58,646 So the only path has length one. So the shortest path distance from SW is 85 00:04:58,646 --> 00:05:00,744 one. Now W is more interesting. 86 00:05:00,744 --> 00:05:05,848 There is a direct one hop path SW that has link four but that is not the 87 00:05:05,848 --> 00:05:10,114 shortest path from S to W. In fact the two hop path that goes 88 00:05:10,114 --> 00:05:15,568 through V as an intermediary has total path link three which is less than the 89 00:05:15,568 --> 00:05:20,812 link of the direct art from S to W. So therefore the shortest path distance 90 00:05:20,812 --> 00:05:26,011 from S to W is going to be three. And finally for the vertex T there's 91 00:05:26,011 --> 00:05:30,492 three different paths going from S to T, there's the two hop path that goes 92 00:05:30,492 --> 00:05:35,273 through V, there's the two hop path which goes through W, both of those have path 93 00:05:35,273 --> 00:05:38,440 link seven. And then there's the three hop path which 94 00:05:38,440 --> 00:05:43,281 goes through both V and W and that actually has a path length of 1 + 2 + 3 = 95 00:05:43,281 --> 00:05:45,910 6. So despite having the largest number of 96 00:05:45,910 --> 00:05:50,332 edges the zigzag path is in fact the shortest path from S to T and it has 97 00:05:50,332 --> 00:05:52,517 length six. Alright so before I tell you how 98 00:05:52,517 --> 00:05:56,127 Dijkstra's algorithm works I feel like I should justify the existence of this 99 00:05:56,127 --> 00:05:59,921 video a little bit alright because this is not the first time we've seen shortest 100 00:05:59,921 --> 00:06:03,763 paths you might be thinking rightfully so we already know how to compute shortest 101 00:06:03,763 --> 00:06:06,540 path's that was one of the applications of Breadth-first search. 102 00:06:06,540 --> 00:06:09,891 So the answer to this question is both yes and no. 103 00:06:09,891 --> 00:06:14,917 Breadth-first search does indeed compute shortest paths we had an entire video 104 00:06:14,917 --> 00:06:19,944 about that but it works only in the special case where the length of every 105 00:06:19,944 --> 00:06:24,053 edge of the graph is one. At the moment we're trying to solve a 106 00:06:24,053 --> 00:06:27,513 more general problem. We're trying to solve shortest paths. 107 00:06:27,513 --> 00:06:30,540 When edges can have arbitrary non negative edge lengths. 108 00:06:30,540 --> 00:06:35,247 So for example, in the graph that we explored in the previous quiz, if we ran 109 00:06:35,247 --> 00:06:38,221 Breadth-first search, starting from the vertex S. 110 00:06:38,221 --> 00:06:42,866 It would say that the shortest path distance from S to T is 2 and that's 111 00:06:42,866 --> 00:06:46,273 because there's a path with two hops going from S to T. 112 00:06:46,273 --> 00:06:50,919 Put differently, T is in the second layer, emanating from S but as we saw in 113 00:06:50,919 --> 00:06:55,441 the quiz, there is not in fact, a shortest two hop path from S to T if you 114 00:06:55,441 --> 00:06:59,343 care about the edge lengths. Rather, the minimum length path, the 115 00:06:59,343 --> 00:07:04,277 shortest path, with respect to the edge weights, is this three hop path which has 116 00:07:04,277 --> 00:07:08,880 a total length of six, so Breadth-first search is not going to give us what we 117 00:07:08,880 --> 00:07:11,750 want, when the edge lengths are not all the same. 118 00:07:11,750 --> 00:07:15,534 And if you think about an application like driving directions then needless to 119 00:07:15,534 --> 00:07:18,648 say it's not the case that every edge in the network is the same. 120 00:07:18,648 --> 00:07:22,433 Some roads are much longer than others. Some roads will have much larger travel 121 00:07:22,433 --> 00:07:25,211 times than others. So, we really do need to solve this more 122 00:07:25,211 --> 00:07:28,277 general shortest path problem. Similarly, if you're thinking more 123 00:07:28,277 --> 00:07:32,253 abstractly about a sequence of decisions like financial transactions in general, 124 00:07:32,253 --> 00:07:34,649 different transactions will have different values. 125 00:07:34,649 --> 00:07:38,146 So, you really want to solve general shortest paths and you're not in the 126 00:07:38,146 --> 00:07:40,350 special case that Breadth-first search solves. 127 00:07:40,350 --> 00:07:45,090 Now, if you're feeling particularly sharp today, you might have the following 128 00:07:45,090 --> 00:07:48,450 objection to what I just said. You might say big deal. 129 00:07:48,450 --> 00:07:52,175 General edge weights, unit edge weights, it's basically the same. 130 00:07:52,175 --> 00:07:54,718 Say you have an edge that has length three. 131 00:07:54,718 --> 00:07:59,449 How is that fundamentally different than having a path with three edges, each of 132 00:07:59,449 --> 00:08:02,939 which has length one? So why not just replace all the edges 133 00:08:02,939 --> 00:08:05,718 with a path of edges of the appropriate length? 134 00:08:05,718 --> 00:08:10,627 Now we have a network in which every edge has unit lengths and now we can just run 135 00:08:10,627 --> 00:08:13,998 Breadth-first search. So, put succinctly, isn't it the case 136 00:08:13,998 --> 00:08:18,492 that computing shortest path with general edge weights reduces to computing 137 00:08:18,492 --> 00:08:23,189 shortest paths with unit edge weights? Well, the first comment I want to make is 138 00:08:23,189 --> 00:08:26,490 I think this would be an excellent objection to raise and indeed as 139 00:08:26,490 --> 00:08:30,082 programmers, as computer scientists, this is the way you should be thinking. 140 00:08:30,082 --> 00:08:33,673 If you see a problem that seems superficially harder than another one you 141 00:08:33,673 --> 00:08:37,605 always want to ask well, maybe just with a, with a clever trick I can reduce it to 142 00:08:37,605 --> 00:08:41,342 a problem I already know how to solve. That's a great attitude in general for 143 00:08:41,342 --> 00:08:45,079 problem solving and indeed, you know if all of the edge links were just small 144 00:08:45,079 --> 00:08:48,700 numbers like one, two and three and so on, this trick would work fine. 145 00:08:48,700 --> 00:08:52,333 The issue is when you have a network where the different edges can have very 146 00:08:52,333 --> 00:08:54,975 different lengths. And that's certainly the case in many 147 00:08:54,975 --> 00:08:57,523 applications. definitely road networks would be one, 148 00:08:57,523 --> 00:09:00,732 where you have both, sort of long highways, and you have neighborhood 149 00:09:00,732 --> 00:09:03,044 streets. And potentially, in financial transaction 150 00:09:03,044 --> 00:09:06,913 based networks you would also have a wide variance between the value of different 151 00:09:06,913 --> 00:09:09,320 transactions. And the problem, then, is some of these 152 00:09:09,320 --> 00:09:11,632 edge links might be really big. There might be 100, 153 00:09:11,632 --> 00:09:15,123 there might be 1,000. It's very hard to put bounds on how large 154 00:09:15,123 --> 00:09:18,440 these edge weights could be. So if you start once in we're replacing 155 00:09:18,440 --> 00:09:21,750 single edges with these really long paths of with the thousand, 156 00:09:21,750 --> 00:09:24,439 you've blown up the size of your graph way too much. 157 00:09:24,439 --> 00:09:28,265 So you do have a faithful representation of your old network but it's too 158 00:09:28,265 --> 00:09:30,178 wasteful. So your going to end up Breadth-first 159 00:09:30,178 --> 00:09:34,211 search in a linear time it's now on this much larger graph and we much prefer 160 00:09:34,211 --> 00:09:38,348 something which is linear time or almost linear time that works directly on the 161 00:09:38,348 --> 00:09:40,210 original graph. And that's exactly... 162 00:09:40,210 --> 00:09:43,970 That Dijkstra's shortest path algorithm is going to accomplish. 163 00:09:43,970 --> 00:09:48,830 Let's now move onto the pseudo code for Dijkstra's shortest path algorithm. 164 00:09:48,830 --> 00:09:52,147 So this is another one of those algorithms, where, no matter how many 165 00:09:52,147 --> 00:09:54,976 times I explain it, it's always just super fun to teach. 166 00:09:54,976 --> 00:09:58,732 And the main reason is, because it exposes the beauty that pops up, in good 167 00:09:58,732 --> 00:10:01,415 algorithm design. So, the pseudo code, as you'll see in a 168 00:10:01,415 --> 00:10:04,732 second is, itself, very elegant. We're just goin got have one loop and in 169 00:10:04,732 --> 00:10:08,488 each iteration of the loop, we will compute the shortest path distance to one 170 00:10:08,488 --> 00:10:11,220 additional vertex. And by the end of the loop, we'll have 171 00:10:11,220 --> 00:10:13,464 computed shortest path distances to everybody. 172 00:10:13,464 --> 00:10:17,561 The proof of correctness which we'll do in the next video is a little bit subtle 173 00:10:17,561 --> 00:10:21,122 but also quite natural, quite pretty. And then, finally, Dijkstra's Algorithm 174 00:10:21,122 --> 00:10:25,456 will give us our first opportunity. See the inner play between good algorithm 175 00:10:25,456 --> 00:10:30,209 design and good data structure design. So with a suitable application of the 176 00:10:30,209 --> 00:10:35,150 heap data structure we'll be able to implement Dijkstra's algorithm so it runs 177 00:10:35,150 --> 00:10:38,590 blazingly fast, almost linear time, namely N times log N. 178 00:10:38,590 --> 00:10:42,712 But I'm getting a little ahead of myself. Let me actually show you this pseudo 179 00:10:42,712 --> 00:10:45,065 code. At a high level you really should think 180 00:10:45,065 --> 00:10:49,289 of Dijkstra's algorithm as being a close cousin as Breadthfirst search and indeed 181 00:10:49,289 --> 00:10:52,749 if all the edge links are equal to one Dijkstra's algorithm becomes 182 00:10:52,749 --> 00:10:55,904 Breadth-first search. So this is sort of a slip generalization 183 00:10:55,904 --> 00:10:58,907 Breadth-first search when edges can have different lengths. 184 00:10:58,907 --> 00:11:02,570 So like our generic graph search procedures we're going to start at the 185 00:11:02,570 --> 00:11:06,285 source vertex S and each iteration we're going to conquer one new vertex. 186 00:11:06,285 --> 00:11:10,102 And we'll do that once each iteration after N - 1 iterations will be done. 187 00:11:10,102 --> 00:11:14,173 And each iteration will correctly compute the shortest path distance to one new 188 00:11:14,173 --> 00:11:18,780 possible destination vertex V. So let me just start by initializing some 189 00:11:18,780 --> 00:11:23,704 notation so capital X is going to denote the vertices we've dealt with so far and 190 00:11:23,704 --> 00:11:27,897 by dealt with I mean we've correctly computed shortest path distance from the 191 00:11:27,897 --> 00:11:31,714 source vertex to every vertex in X. We're going to augment X by one new 192 00:11:31,714 --> 00:11:34,025 vertex in each generation of the main loop. 193 00:11:34,025 --> 00:11:37,842 Remember, that we're responsible for outputting in numbers one for each 194 00:11:37,842 --> 00:11:41,928 vertex, we're not just computing one thing, we're computing the shortest path 195 00:11:41,928 --> 00:11:44,938 distance from the source vertex S to every other vertex. 196 00:11:44,938 --> 00:11:48,486 So I'm going to frame the output in terms of this array capital A. 197 00:11:48,486 --> 00:11:52,733 So for each vertex we're going to have an entry in the array A and the goal is at 198 00:11:52,733 --> 00:11:55,966 the end of the. A will be populated with the correct 199 00:11:55,966 --> 00:11:59,901 shortest path distances. Now, to help you understand Dijkstra's 200 00:11:59,901 --> 00:12:02,143 algorithm, I'm going to do some additional 201 00:12:02,143 --> 00:12:05,986 bookkeeping which you would not do in a real implementation of Dijkstra's 202 00:12:05,986 --> 00:12:08,601 algorithm. Specifically, in addition to this array, 203 00:12:08,601 --> 00:12:12,871 capital A in which we compute shortest path distances from the source vertex to 204 00:12:12,871 --> 00:12:16,234 every other destination. There's going to be an array, capital B 205 00:12:16,234 --> 00:12:20,348 in which we'll keep track of the actual shortest path itself from the source 206 00:12:20,348 --> 00:12:24,212 vertex S to each destination V. So, the arrays A and B will be indexed in 207 00:12:24,212 --> 00:12:27,056 the same way. There'll be one entry for each possible 208 00:12:27,056 --> 00:12:30,276 destination vertex V. Capital A will store just a number for 209 00:12:30,276 --> 00:12:32,530 each destination's shortest path distance. 210 00:12:32,530 --> 00:12:36,823 The array B in each position will store an actual path, to the path, the shortest 211 00:12:36,823 --> 00:12:39,881 path from S to V. But again, you would not include this in 212 00:12:39,881 --> 00:12:43,316 an actual implementation. I just find, it's, in my experience, it's 213 00:12:43,316 --> 00:12:47,609 easier for students to understand this algorithm if we think of the paths being 214 00:12:47,609 --> 00:12:51,047 carried along as well. So now that I've told you the semantics 215 00:12:51,047 --> 00:12:55,280 of these two arrays, I hope it's no surprise how we initialize them for the 216 00:12:55,280 --> 00:12:58,835 source vertex itself, S. the shortest path distance from S to 217 00:12:58,835 --> 00:13:01,996 itself is zero. The empty path gets you from S to S with 218 00:13:01,996 --> 00:13:04,987 length zero. There's no negative edges by assumptions. 219 00:13:04,987 --> 00:13:09,784 There's no way you can get from S back to S with a non-positive length, so this is 220 00:13:09,784 --> 00:13:12,267 definitely the shortest path distance for S. 221 00:13:12,267 --> 00:13:16,725 By the same reasoning, the shortest path from S to S is just the empty path, the 222 00:13:16,725 --> 00:13:20,337 path with no edges in it. So now let's proceed to the main while 223 00:13:20,337 --> 00:13:22,876 loop. So then plan is we want to grow this set 224 00:13:22,876 --> 00:13:27,388 capital X like a mold until it covers the entire graph so with each iteration its 225 00:13:27,388 --> 00:13:31,845 going to grow and cover up one new vertex and that vertex will then be processed 226 00:13:31,845 --> 00:13:35,972 and at the time of processing we're responsible for computing the shortest 227 00:13:35,972 --> 00:13:40,044 path distance from S to this vertex and also figuring out what the actual 228 00:13:40,044 --> 00:13:44,341 shortest path from S to this vertex is. So in each iteration, we need to grow x 229 00:13:44,341 --> 00:13:46,769 by one node to ensure that we make progress. 230 00:13:46,769 --> 00:13:49,693 So the obvious question is, which node should we pick? 231 00:13:49,693 --> 00:13:53,280 Which one do we add to x next? So there's going to be two ideas here. 232 00:13:53,280 --> 00:13:57,639 The first one we've already seen in terms of all of these generic graph search 233 00:13:57,639 --> 00:14:00,232 procedures. Which is, we're going to look at the 234 00:14:00,232 --> 00:14:02,991 edges and the vertices that which on the frontier. 235 00:14:02,991 --> 00:14:07,460 So we're going to look at the vertices that are just one hope away from vertices 236 00:14:07,460 --> 00:14:11,005 we've already put into x. So that motivates it, in given ideration 237 00:14:11,005 --> 00:14:14,850 of the wild loop, so look at the stuff we've already processed, that's X. 238 00:14:14,850 --> 00:14:18,134 And the stuff we haven't already processed, that's V - X. 239 00:14:18,134 --> 00:14:21,473 S of course, starts in X and we never take any thing out of X. 240 00:14:21,473 --> 00:14:24,648 So S is still there. You know, in some generic iteration of 241 00:14:24,648 --> 00:14:28,097 the while loop, we might have some other vertices that are in X. 242 00:14:28,097 --> 00:14:32,039 And in the generic iteration of this while loop, there might be multiple 243 00:14:32,039 --> 00:14:35,488 vertices which are not in X. And now, as we've seen in our graph 244 00:14:35,488 --> 00:14:39,473 search procedures, there are general edges crossing this cut. So, there are 245 00:14:39,473 --> 00:14:43,522 edges which have one endpoint in each side, one endpoint in X and one endpoint 246 00:14:43,522 --> 00:14:46,118 outside of X. This is a directed graph so they can 247 00:14:46,118 --> 00:14:49,544 cross in two directions. They can cross from left to right or they 248 00:14:49,544 --> 00:14:53,480 can cross from right to left. So you might have some edges internal to 249 00:14:53,480 --> 00:14:56,621 X those are things we don't care about at this point. 250 00:14:56,621 --> 00:15:01,600 You might have edges which are internal to V - X we also don't care about those 251 00:15:01,600 --> 00:15:05,334 at least not quite yet. And then you have edges which can cross 252 00:15:05,334 --> 00:15:09,005 from X to V - X. As well as edges that can cross in the 253 00:15:09,005 --> 00:15:13,850 reverse direction from V - X back to X. And the ones we're going to be interested 254 00:15:13,850 --> 00:15:18,439 in, just like when we did graph search and directed graphs, are the edges 255 00:15:18,439 --> 00:15:22,519 crossing from left to right. The edges whose tail is amongst the 256 00:15:22,519 --> 00:15:26,853 vertices we've already seen. And whose head is some not yet explored 257 00:15:26,853 --> 00:15:30,134 vertex. So the first idea is that at each 258 00:15:30,134 --> 00:15:35,717 iteration of the while loop we scan or we examine all of the edges with tail and X 259 00:15:35,717 --> 00:15:40,959 and head outside of X one of those is going to lead us to the vertex that we 260 00:15:40,959 --> 00:15:44,494 pick next. So that's the first idea but now we need 261 00:15:44,494 --> 00:15:47,323 a second idea because this is again quite undetermined. 262 00:15:47,323 --> 00:15:51,705 There could be multiple such vertices which meet this criterion, so for example 263 00:15:51,705 --> 00:15:56,364 in the cartoon in the bottom left part of this slide you'll notice that there's one 264 00:15:56,364 --> 00:16:00,833 vertex here which is the head of an arc that crosses from left to right, and 265 00:16:00,833 --> 00:16:05,588 there's yet another vertex down here, in D minus X, which again is the head of an 266 00:16:05,588 --> 00:16:09,986 arc, which crosses from left to right. So there are two options, of which of 267 00:16:09,986 --> 00:16:14,681 those two does suck into are set X, and we might want some guidance about which 268 00:16:14,681 --> 00:16:18,068 one to pick next. So the key ideal in dijkstra, is to give 269 00:16:18,068 --> 00:16:22,763 each vertex a score corresponding to how close that vertex seems to the source 270 00:16:22,763 --> 00:16:27,221 vertex S and then to pick, among all candidat vertices, the one that has the 271 00:16:27,221 --> 00:16:29,420 minimum score. Let me be more precise. 272 00:16:29,420 --> 00:16:35,217 So among all crossing edges, with tail on the left side and head on the right side, 273 00:16:35,217 --> 00:16:40,185 we pick the edge. The minimizes the following criterion, 274 00:16:40,185 --> 00:16:46,475 the shortest path distance that we previously computed from S to the vertex 275 00:16:46,475 --> 00:16:50,696 V, plus the length of the edge that connects V to W. 276 00:16:50,696 --> 00:16:57,235 So this is quite an important expression so I will call this Dijkstra's greedy 277 00:16:57,235 --> 00:17:01,125 criterion. This is a very good idea to use this 278 00:17:01,125 --> 00:17:06,340 method to choose which vertex to add to the set X, as we'll see. 279 00:17:06,340 --> 00:17:12,493 I need to give a name to this edge, which minimizes this quantity over all crossing 280 00:17:12,493 --> 00:17:17,405 edges, so it's call B star, W star. So for example in the cartoon in the 281 00:17:17,405 --> 00:17:21,870 bottom left maybe of the two edges crossing from left to right maybe the top 282 00:17:21,870 --> 00:17:26,625 one is the one that has a smaller value of Dijkstra's greedy criterion so in that 283 00:17:26,625 --> 00:17:31,438 case this would be the vertex V star and at the other end of the edge would be the 284 00:17:31,438 --> 00:17:34,553 vertex W star. So this edge, V star, W star is going to 285 00:17:34,553 --> 00:17:38,329 do wonders for us. It will both guide us to the vertex that 286 00:17:38,329 --> 00:17:41,337 we should add to X next. That's going to be W star. 287 00:17:41,337 --> 00:17:46,200 It's going to tell us how we should compute the shortest path distance to W 288 00:17:46,200 --> 00:17:49,144 star. As well as what the actual shortest path 289 00:17:49,144 --> 00:17:53,048 from S to W star is. So specifically, in this iteration of the 290 00:17:53,048 --> 00:17:56,184 while loop. After we've chosen this edge, V star, W 291 00:17:56,184 --> 00:17:57,720 star. We add W star to X. 292 00:17:57,720 --> 00:18:02,257 Remember, by definition W Star was previously not in capital X, so we're 293 00:18:02,257 --> 00:18:06,220 making progress by adding it to X, that's one more vertex in X. 294 00:18:06,220 --> 00:18:10,377 Now, X is supposed to represent all of the nodes that we've already processed. 295 00:18:10,377 --> 00:18:14,372 So, an invariant of this algorithm is that we've computed shortest path 296 00:18:14,372 --> 00:18:17,935 distances for everybody in X as well as the actual shortest paths. 297 00:18:17,935 --> 00:18:21,823 So, now that we're putting W star in X, we're responsible for all of this 298 00:18:21,823 --> 00:18:25,602 information, shortest path information. So, what we're going to do is we're going 299 00:18:25,602 --> 00:18:29,914 to set the, our estimate. Of, W stars shortest path distance from 300 00:18:29,914 --> 00:18:35,183 S, to be equal to the value of this die-strict reading criteria for this 301 00:18:35,183 --> 00:18:38,550 edge. That is, whatever our previously computed 302 00:18:38,550 --> 00:18:44,331 shortest path distance from S to B star was, plus, the length of the direct edge 303 00:18:44,331 --> 00:18:48,869 from B star to W star. Now, a key point is to realize that this 304 00:18:48,869 --> 00:18:53,333 code does make sense. By which I mean, if you think about this 305 00:18:53,333 --> 00:18:56,700 quantity AV, this has been previously computed. 306 00:18:56,700 --> 00:19:00,679 And that's because an invariant in this algorithm is we've always computed 307 00:19:00,679 --> 00:19:03,798 shortest path distances to everything that's in capital X. 308 00:19:03,798 --> 00:19:08,046 And of course, the same thing holds when we need to assign W star shortest path 309 00:19:08,046 --> 00:19:10,734 distance. Because V star was a member of capital X. 310 00:19:10,734 --> 00:19:13,477 We had already computed its shortest path distance. 311 00:19:13,477 --> 00:19:17,080 So we can just look up the V star entry position in the array A. 312 00:19:17,080 --> 00:19:21,033 So over in our picture in our left, we would just say well what did we compute 313 00:19:21,033 --> 00:19:24,987 the shortest path distance to these star previously maybe it's something like 314 00:19:24,987 --> 00:19:29,041 seventeen, then we'd say what is the length of this direct edge from V star to 315 00:19:29,041 --> 00:19:32,285 W star, maybe that's six. Then we would add seventeen and six and 316 00:19:32,285 --> 00:19:36,290 we would put 23 as our estimate of the shortest path distance from S to W star. 317 00:19:36,290 --> 00:19:41,162 So we'll do something analogous with the shortest paths itself, in the array B, 318 00:19:41,162 --> 00:19:46,230 that is again, we're responsible since we just added W star to capital X where 319 00:19:46,230 --> 00:19:50,518 responsible for suggesting a path from S to W star in the B array. 320 00:19:50,518 --> 00:19:55,781 So what we're going to do, is we're just going to, inherit the previously computed 321 00:19:55,781 --> 00:20:00,978 path to V star and we're just going to tack on the end one extra hop, namely the 322 00:20:00,978 --> 00:20:05,916 direct edge from V-star to W-star, that'll give us a path from S all the way 323 00:20:05,916 --> 00:20:09,100 to W-star, via, V-star as an intermediate pit stop. 324 00:20:09,100 --> 00:20:11,429 And that is the entirety of Dijkstra's algorithm. 325 00:20:11,429 --> 00:20:15,184 I've explained all of the ingredients about how it works at a conceptual level. 326 00:20:15,184 --> 00:20:17,941 So the two things I owe you is, you know why is it correct? 327 00:20:17,941 --> 00:20:21,648 Why does it actually compute shortest paths correctly to all of the different 328 00:20:21,648 --> 00:20:24,310 vertices, and then secondly, how fast can we implement it? 329 00:20:24,310 --> 00:20:27,542 So the next two videos are going to answer both of those questions, but 330 00:20:27,542 --> 00:20:31,107 before we do that, let's go through an example, to get a better feel for how 331 00:20:31,107 --> 00:20:34,530 this algorithm actually works, and I also want to go through a non-example. 332 00:20:34,530 --> 00:20:38,304 So that you can appreciate how it breaks down when there are negative edges. 333 00:20:38,304 --> 00:20:41,483 And that'll make it clear why we do need a proof of correctness. 334 00:20:41,483 --> 00:20:45,060 Because it's not correct without any assumptions about the edge lengths.