1 00:00:00,000 --> 00:00:04,442 We've arrived at another one of computer science's greatest hits, namely Dijkstra's 2 00:00:04,442 --> 00:00:08,510 shortest path algorithm. So let me tell you about the problem. It's a problem 3 00:00:08,510 --> 00:00:12,471 called single source, shortest paths. Basically what we wanna do is compute 4 00:00:12,471 --> 00:00:16,431 something like driving directions. So we're given as input a graph, in this 5 00:00:16,431 --> 00:00:20,298 lecture I'm gonna work with directed graphs, although the same algorithm would 6 00:00:20,298 --> 00:00:24,942 work with undirected graphs with cosmetic changes. As usual, we'll use m to denote 7 00:00:24,942 --> 00:00:28,992 the number of edges and N to denote the number of vertices. The input also 8 00:00:28,992 --> 00:00:33,456 includes two extra ingredients. First of all, for each edge E, we're given, as 9 00:00:33,456 --> 00:00:38,158 input, a non negative length, which I'll denote by L sub B. In the context of a 10 00:00:38,158 --> 00:00:42,859 driving directions application, L sub B could denote the, the mileage, how long, 11 00:00:43,038 --> 00:00:48,156 this particular road is, or it could also denote, the expected travel time along the 12 00:00:48,156 --> 00:00:52,917 edge. The second ingredient is a vertex from which we are looking for paths. This 13 00:00:52,917 --> 00:00:57,679 is exactly the same as we had in breadth first search and depth first search. We 14 00:00:57,679 --> 00:01:02,648 have an originating vertex which we'll call here, the source. Our responsibility 15 00:01:02,648 --> 00:01:08,831 then is to given this input to compute for every other vertex V in this network the 16 00:01:08,831 --> 00:01:14,948 length of a shortest path from the source vertex S to that destination vertex V. And 17 00:01:14,948 --> 00:01:19,344 so, just to be clear, what is the length of a path that has, say, three edges in 18 00:01:19,344 --> 00:01:23,669 it? Well, it's just the sum of the length of the first edge in the path, plus the 19 00:01:23,669 --> 00:01:27,396 length of the second edge in the path, plus the length of the third edge in the 20 00:01:27,396 --> 00:01:32,761 path. So if you had a path like this with three edges, and lengths one, two, and 21 00:01:32,761 --> 00:01:37,034 three, then the length of the path would just be six. And then we define the 22 00:01:37,034 --> 00:01:41,569 shortest SV path in the natural way. So amongst all of the paths directed from S 23 00:01:41,569 --> 00:01:46,218 to V each one has its own respective path length. And then the minimum overall SV 24 00:01:46,218 --> 00:01:50,527 paths is the shortest path distance in the graph G. So, I'm going to make two 25 00:01:50,527 --> 00:01:55,006 assumptions for these lectures. One is really just for convenience. The other is 26 00:01:55,006 --> 00:01:59,599 really important. The other assumption without which Dijkstra's algorithm is not 27 00:01:59,599 --> 00:02:03,741 correct, as we'll see. So, for convenience we'll assume that there is a directed path 28 00:02:03,741 --> 00:02:07,360 between S and every other vertex V in the graph. Otherwise the shortest path 29 00:02:07,360 --> 00:02:11,216 distance is something we'd define to be plus infinity. And the reason this is not 30 00:02:11,216 --> 00:02:15,120 a big assumption is if you think about it, you could detect which vertices are not 31 00:02:15,120 --> 00:02:19,167 reachable from S just in a pre processing step using say breadth first or depth first 32 00:02:19,167 --> 00:02:22,553 search and then you could delete the irrelevant part of the graph and run 33 00:02:22,553 --> 00:02:27,726 Dijkstra's algorithm as we'll describe it on what remains. Alternatively Dijkstra's algorithm 34 00:02:27,726 --> 00:02:32,427 will quite naturally figure out which vertices there are paths to from S and which 35 00:02:32,427 --> 00:02:34,911 ones there are not. So this won't really come up. 36 00:02:34,911 --> 00:02:37,792 So, to keep it simple just think about, we have an input graph 37 00:02:37,792 --> 00:02:42,042 where you can get to S to V. For every different vertex V and the challenge then 38 00:02:42,042 --> 00:02:47,335 is amongst all the ways to get from S to V what is the shortest way to do it? So the 39 00:02:47,335 --> 00:02:51,785 second assumption already appears in the problem statement, but I want to reiterate 40 00:02:51,785 --> 00:02:56,885 it just so it's really clear. When we analyze Dijkstra's algorithm, we always 41 00:02:56,885 --> 00:03:01,340 focus on graphs where every length is non-negative. No negative edge lengths are 42 00:03:01,340 --> 00:03:05,767 allowed. And we'll see why a little bit later in the, in the video. Now in the 43 00:03:05,767 --> 00:03:09,150 context of a driving directions application it's natural to ask the 44 00:03:09,150 --> 00:03:13,179 question, why would you ever care about negative edge lengths. Until we invent a time 45 00:03:13,179 --> 00:03:17,308 machine it doesn't seem like negative edge lengths are gonna be relevant when you're 46 00:03:17,308 --> 00:03:21,275 computing literal paths through literal networks. But again remember that paths 47 00:03:21,275 --> 00:03:25,805 can be thought of as more abstractly as a just sequence of decisions. And some of 48 00:03:25,805 --> 00:03:30,424 the most powerful applications of shortest paths are coming up with optimal ways such 49 00:03:30,424 --> 00:03:34,285 sequences. So, for example, maybe you're engaging in financial transactions, and 50 00:03:34,285 --> 00:03:38,296 you have the option of both buying and selling assets at different times. But if 51 00:03:38,296 --> 00:03:41,956 you sell, then you get some kind of profit, and that would correspond to a 52 00:03:41,956 --> 00:03:45,666 negative edge length. So there are quite interesting applications in which 53 00:03:45,666 --> 00:03:49,627 negative edge lengths are relevant. If you are dealing with such an application, 54 00:03:49,627 --> 00:03:53,739 Dijkstra's algorithm is not the algorithm to use. There is a different shortest path 55 00:03:53,739 --> 00:03:57,549 algorithm, a couple other ones, but the most well known one is called Bellman 56 00:03:57,549 --> 00:04:01,623 Ford. That's something based on dynamic programming, which we may well cover in a 57 00:04:01,623 --> 00:04:06,384 sequel course. Okay, So for Dijkstra's algorithm we always focus on graphs that 58 00:04:06,384 --> 00:04:12,571 have only non negative edge lengths. So for the next quiz I just wanna make sure 59 00:04:12,571 --> 00:04:16,896 that you understand the single source shortest path problem. Okay let me draw 60 00:04:16,896 --> 00:04:20,793 for you here a simple four-node network and ask you for what are the four shortest 61 00:04:20,793 --> 00:04:25,770 path lengths. So from the source for text S to each of the four vertices in the network. 62 00:04:26,970 --> 00:04:30,881 Alright, so the answer to this quiz is the final option, zero, one, 63 00:04:30,881 --> 00:04:35,993 three, six. To see why that's true, well all of the options had zero as the 64 00:04:35,993 --> 00:04:41,429 shortest path distance from S to itself so that just seemed kinda obvious. So the 65 00:04:41,429 --> 00:04:46,830 empty path will get you from S to itself and have zero length. Now suppose you 66 00:04:46,830 --> 00:04:51,717 wanted to get from S to V. Well, there's actually only one way to do that, you have 67 00:04:51,717 --> 00:04:57,176 to go along this one hop path. So the only path has length one. So, the shortest path 68 00:04:57,176 --> 00:05:02,550 distance from S to V is one. Now W's more interesting. There's a direct one hop 69 00:05:02,550 --> 00:05:07,923 path, SW, that has length four. But that is not the shortest path from S to W. In 70 00:05:07,923 --> 00:05:13,504 fact, the two hop path, that goes through V as an intermediary, has total path length 71 00:05:13,504 --> 00:05:18,946 three, which is less than the length of the direct arc from S to W. So therefore, 72 00:05:18,946 --> 00:05:24,968 the shortest path distance from S to W is going to be three. And finally, for the 73 00:05:24,968 --> 00:05:29,741 vertex T, there's three different paths going from S to T. There's the T, two hop 74 00:05:29,741 --> 00:05:34,207 path that goes through V. There's the two hop path which goes through W. Both of 75 00:05:34,207 --> 00:05:37,692 those have path length seven. And then there's the three hop path which goes 76 00:05:37,692 --> 00:05:41,432 through both V and W, and that actually has a path length of one plus two plus 77 00:05:41,432 --> 00:05:45,128 three equals six. So despite having the largest number of edges, the zigzag path 78 00:05:45,128 --> 00:05:51,460 is, in fact, t he shortest path from S to T, and it has length six. Alright. So 79 00:05:51,460 --> 00:05:55,174 before I tell you how Dijkstra's algorithm works, I feel like I should justify the 80 00:05:55,174 --> 00:05:58,655 existence of this video a little bit. Alright, Because this is not the first 81 00:05:58,655 --> 00:06:02,275 time we've seen shortest paths. You might be thinking, rightfully so. We already 82 00:06:02,275 --> 00:06:05,896 know how to compute shortest paths. That was one of the applications of breadth 83 00:06:05,896 --> 00:06:10,685 first search. So the answer to this question is both yes and no. Breadth first 84 00:06:10,685 --> 00:06:15,363 search does indeed compute shortest paths. We had an entire video about that. But it 85 00:06:15,363 --> 00:06:21,714 works only in the special case where the length of every edge of the graph is one. 86 00:06:21,714 --> 00:06:26,560 At the moment we're trying to solve a more general problem. We're trying to solve 87 00:06:26,560 --> 00:06:30,912 shortest paths when edges can have arbitrary non negative edge lengths. So for 88 00:06:30,912 --> 00:06:35,295 example, in the graph that we'd explored in the previous quiz, if we ran 89 00:06:35,295 --> 00:06:40,171 breadth-first search, starting from the vertex S, it would say that the shortest 90 00:06:40,171 --> 00:06:44,863 path distance from S to T is two. And that's because there's a path with two 91 00:06:44,863 --> 00:06:49,863 hops going from S to T, put differently, T is in the second layer emanating from S. 92 00:06:49,863 --> 00:06:54,987 But as we saw in the quiz, there is not in fact a shortest two hop path from S to T 93 00:06:54,987 --> 00:06:59,308 if you care about the edge lengths, rather, the minimum length path, the 94 00:06:59,308 --> 00:07:04,227 shortest path, with respect to the edge weights, is this three hop path, Which has 95 00:07:04,227 --> 00:07:08,830 a total length of six. So breadth first search is not going to give us what we 96 00:07:08,830 --> 00:07:13,253 want, when the edge lengths are not all the same. And if you think about an 97 00:07:13,253 --> 00:07:17,138 application like driving directions, then needless to say, it's not the case that 98 00:07:17,138 --> 00:07:20,877 every edge in the network is the same. Some roads are much longer than others, 99 00:07:20,877 --> 00:07:24,713 some roads will have much larger travel times than others; so we really do need to 100 00:07:24,713 --> 00:07:28,597 solve this more general shortest path problem. Similarly if you're thinking more 101 00:07:28,597 --> 00:07:32,628 abstractly about a sequence of decisions like financial transactions, in general, 102 00:07:32,628 --> 00:07:35,938 different transactions will have different values; so you really want to solve 103 00:07:35,938 --> 00:07:40,526 general shortest paths not in the special case that breadth first search solves. Now 104 00:07:40,526 --> 00:07:44,950 if you're feeling particularly sharp today, you might have the following 105 00:07:44,950 --> 00:07:49,182 objection to what I've just said. You might say, yeah, big deal. General edge 106 00:07:49,182 --> 00:07:53,935 weights, unit edge weights. It's basically the same. Say you have an edge that has 107 00:07:53,935 --> 00:07:58,629 length three. How is that fundamentally different than having a path with three 108 00:07:58,629 --> 00:08:03,382 edges, each of which has length one? So why not just replace all the edges with a 109 00:08:03,382 --> 00:08:08,253 path of edges of the appropriate length? Now we have a network in which every edge 110 00:08:08,253 --> 00:08:12,888 has unit length and now we can just run breadth first search. So, put succinctly, 111 00:08:12,888 --> 00:08:17,938 isn't it the case that computing shortest paths with general edge weights reduces to 112 00:08:17,938 --> 00:08:22,547 computing shortest paths with unit edge weights? Well the first comment I want to 113 00:08:22,547 --> 00:08:26,327 make is I think this will be an excellent objection to raise. Indeed, as 114 00:08:26,327 --> 00:08:30,641 programmers, as computer scientists this is the way you should be thinking. If you 115 00:08:30,641 --> 00:08:34,462 see a problem that seems superficially harder than another one, you always want 116 00:08:34,462 --> 00:08:38,607 to ask. Maybe with a clever trick I can reduce it to a problem I already know how 117 00:08:38,607 --> 00:08:42,468 to solve. That's a great attitude in general for problem solving. And indeed if 118 00:08:42,468 --> 00:08:47,468 all of the edge lengths were just small numbers like 1,2 and 3 and so on, this trick 119 00:08:47,468 --> 00:08:51,642 would work fine. The issue is when you have a network where the different edges 120 00:08:51,642 --> 00:08:55,477 can have very different lengths. And that's certainly the case in many applications. 121 00:08:55,619 --> 00:08:58,980 Definitely road networks would be one, where you have both, sort of, long 122 00:08:58,980 --> 00:09:02,389 highways and you have neighborhood streets. And potentially, in financial 123 00:09:02,389 --> 00:09:06,318 transaction based networks, you would also have a wide variance between the value of 124 00:09:06,318 --> 00:09:10,153 different transactions. And the problem then is, some of these edge lengths might be 125 00:09:10,153 --> 00:09:13,487 really big. They might be a 100. They might be a 1000. It's very hard to put 126 00:09:13,487 --> 00:09:17,160 a priori bounds on how large these edge weights could be. So if you start. 127 00:09:17,160 --> 00:09:21,475 wantonly replacing single edges with these really long paths of length 1,000, you've 128 00:09:21,475 --> 00:09:25,212 blown up the size of your graph way too much. So you do have a faithful 129 00:09:25,212 --> 00:09:29,423 representation of your old network, but it's too wasteful. So even though breadth 130 00:09:29,423 --> 00:09:33,738 first search runs in linear time, it's now on this much larger graph, and we'd much 131 00:09:33,738 --> 00:09:38,107 prefer something which is linear time or almost linear time that works directly on 132 00:09:38,107 --> 00:09:42,733 the original graph and that is exactly what Dijkstra's shortest path algorithm is 133 00:09:42,733 --> 00:09:47,818 going to accomplish. Let's now move on to the pseudocode for Dijkstra's shortest 134 00:09:47,818 --> 00:09:52,077 path algorithm. So this is another one of those algorithms where no matter how many 135 00:09:52,077 --> 00:09:55,854 times I explain it, it's super fun to teach. And the main reason is because it 136 00:09:55,854 --> 00:09:59,730 exposes the beauty that pops up in good algorithm design. So, the pseudo code, as 137 00:09:59,730 --> 00:10:03,655 you'll see in a second, is itself very elegant. We're just going to have one loop 138 00:10:03,655 --> 00:10:07,727 and then in each iteration of the loop, we will compute the shortest path distance 139 00:10:07,727 --> 00:10:11,428 to one additional vertex. And by the end of the loop we'll have completed shortest 140 00:10:11,428 --> 00:10:14,984 path distances to everybody. The proof of correctness, which we'll do in the next 141 00:10:14,984 --> 00:10:19,453 video, is a little bit subtle but also quite natural, quite pretty. And then 142 00:10:19,453 --> 00:10:23,296 finally, Dijkstra's algorithm will give us our first opportunity to see the 143 00:10:23,296 --> 00:10:28,423 interplay between good algorithm design and good data structure design. So with a 144 00:10:28,423 --> 00:10:32,632 suitable application of the heap data structure, we'll be able to implement 145 00:10:32,632 --> 00:10:37,216 Dijkstra's algorithm so it runs blazingly fast, almost linear time. Namely, M times 146 00:10:37,216 --> 00:10:42,323 log N. But I'm getting a little ahead of myself. Let me actually show you the 147 00:10:42,323 --> 00:10:45,847 pseudo code. At a high level, you really should think of Dijkstra's algorithm as 148 00:10:45,847 --> 00:10:49,862 being a close cousin of breadth first search. And indeed, if all of the edge 149 00:10:49,862 --> 00:10:53,604 lengths are equal to one, Dijkstra's algorithm becomes breadth first search. So 150 00:10:53,604 --> 00:10:57,690 this is sort of a slick generalization of breadth first search when edges can have 151 00:10:57,690 --> 00:11:01,481 different lengths. So, like our generic graph search procedures, we're going to 152 00:11:01,481 --> 00:11:05,518 start at the source for a text S. And in each iteration, we're going to conquer one 153 00:11:05,518 --> 00:11:09,358 new vertex. And we'll do that once each iteration after N minus one iterations, 154 00:11:09,358 --> 00:11:12,613 we'll be done. And in each iteration, we'll correctly comp ute the shortest path 155 00:11:12,613 --> 00:11:17,391 distance to one new possible destination vertex, V. So let me just start by 156 00:11:17,391 --> 00:11:22,455 initializing some notation. So capital X is going to denote the vertices we've 157 00:11:22,455 --> 00:11:26,555 dealt with so far. And by dealt with I mean we've correctly computed shortest 158 00:11:26,555 --> 00:11:31,144 path distance from the source vertex to every vertex in X. We're going to augment 159 00:11:31,144 --> 00:11:35,400 X by one new vertex in each iteration of the main loop. Remember that we're 160 00:11:35,400 --> 00:11:39,482 responsible for outputting N numbers, one for each vertex. Were not just computing 161 00:11:39,482 --> 00:11:43,595 one thing we're computing the shortest path distance from the source vertex S to 162 00:11:43,595 --> 00:11:47,908 every other vertex. So, I'm going to frame the output in terms of this array capital 163 00:11:47,908 --> 00:11:52,275 A. So for each vertex we're going to have an entry in this array A and the goal is 164 00:11:52,275 --> 00:11:56,642 at the end of the algorithm, A will be populated with the correct shortest 165 00:11:56,642 --> 00:12:01,487 path distances. Now to help you understand Dijkstra's algorithm, I'm gonna do some 166 00:12:01,487 --> 00:12:06,056 additional bookkeeping which you would not do in a real implementation of Dijkstra's 167 00:12:06,056 --> 00:12:10,302 algorithm. Specifically, in addition to this array capital A, in which we compute 168 00:12:10,302 --> 00:12:14,656 shortest path distances from the source vertex to very other destination, there's 169 00:12:14,656 --> 00:12:19,063 gonna be an array capital B in which we'll keep track of the actual shortest path 170 00:12:19,063 --> 00:12:23,383 itself, from the source vertex S to each destination V. So the arrays A and B will 171 00:12:23,383 --> 00:12:27,593 be indexed in the same way. There'll be one entry for each possible destination 172 00:12:27,593 --> 00:12:31,910 vertex V. Capital A will store just a number for each destination's shortest path 173 00:12:31,910 --> 00:12:35,960 distance. The array B in each position will store an actual path, so the path, 174 00:12:35,960 --> 00:12:40,223 the shortest path from S to V. But again, you would not include this in an actual 175 00:12:40,223 --> 00:12:44,060 implementation. I just find in my experience it's easier for students to 176 00:12:44,060 --> 00:12:48,483 understand this algorithm if we think of the paths being carried along as 177 00:12:48,483 --> 00:12:52,506 well. So now that I've told you the semantics of these two arrays, I hope it's 178 00:12:52,506 --> 00:12:57,453 no surprise how we initialize them for the source vertex itself S. The shortest path 179 00:12:57,453 --> 00:13:01,692 distance from S to itself is zero, the empty path gets you from S to S with 180 00:13:01,692 --> 00:13:05,906 length zero, there's no negative edges by assumption, so there's no way you can get 181 00:13:05,906 --> 00:13:10,819 from S back to S with non positive length, so this is definitely the shortest path 182 00:13:10,819 --> 00:13:14,684 distance for S. By the same reasoning, the shortest path from S to S is just the 183 00:13:14,684 --> 00:13:20,287 empty path, the path with no edges in it. So now let's proceed to the main while 184 00:13:20,287 --> 00:13:24,839 loop. So the plan is we wanna grow this set capital X like a mold that covers the 185 00:13:24,839 --> 00:13:29,388 entire graph. So in each iteration it's going to grow and cover up one new vertex 186 00:13:29,388 --> 00:13:33,601 and that vertex will then be processed and at the time of processing we're 187 00:13:33,601 --> 00:13:37,839 responsible for computing the shortest path distance from S to this vertex and 188 00:13:37,839 --> 00:13:42,743 also figuring out what the actual shortest path from S to this vertex is. So in each 189 00:13:42,743 --> 00:13:47,239 iteration we need to grow X by one node to ensure that we've made progress. So the 190 00:13:47,239 --> 00:13:51,626 obvious question is, which node should we pick? Which one do we add the X next? So 191 00:13:51,626 --> 00:13:56,232 there's gonna be two ideas here. The first one we've already seen in terms of all of 192 00:13:56,232 --> 00:14:00,619 these generic graph search procedures, which is we're going to look at the edges 193 00:14:00,619 --> 00:14:04,779 and vertices which are on the frontier. So we're going to look at the vertices that 194 00:14:04,779 --> 00:14:09,235 are just one hop away from the vertices we've already put into X. So that 195 00:14:09,235 --> 00:14:13,750 motivates at a given iteration of the while loop to look at the stuff we've already 196 00:14:13,750 --> 00:14:17,954 processed that's X. And the stuff we haven't already processed, that's V minus 197 00:14:17,954 --> 00:14:22,128 X. S of course starts in X and we never taken anything out of X so S is still 198 00:14:22,128 --> 00:14:26,086 there, you know. And some generic iteration of the while loop, we might have 199 00:14:26,086 --> 00:14:30,369 some other vertices that are in X. And in a generic iteration of this while loop, 200 00:14:30,369 --> 00:14:34,923 there might be multiple vertices which are not in X. And now as we've seen in our 201 00:14:34,923 --> 00:14:39,362 graph search procedures there in general are edges crossing this cut, so there are 202 00:14:39,362 --> 00:14:43,533 edges which have one end point in each side, one end point in X and one end point 203 00:14:43,533 --> 00:14:47,807 outside of X. This is a directed graph so they can cross in two directions, they can 204 00:14:47,807 --> 00:14:52,364 cross from left to right or they can cross from right to left. So you might have some 205 00:14:52,364 --> 00:14:56,990 edges internal to X. Those are things we don't care about at this point. You 206 00:14:56,990 --> 00:15:00,308 might have edges which are internal to V minus X. We don't care about those, at 207 00:15:00,324 --> 00:15:06,480 least not quite yet. And then you have edges which can cross from X to V minus X. 208 00:15:06,480 --> 00:15:11,472 As well as edges that can cross in the reverse direction from V minus X back to 209 00:15:11,472 --> 00:15:16,464 X. And the ones we're gonna be interested in, just like when we did graph search 210 00:15:16,464 --> 00:15:20,326 on directed graphs, are the edges crossing from left to right. The edges 211 00:15:20,326 --> 00:15:24,811 whose tail is amongst the vertices we've already seen and whose head is some not 212 00:15:24,811 --> 00:15:31,312 yet explored vertex. So the first idea is that at each iteration of the while loop 213 00:15:31,312 --> 00:15:37,691 we scan or we examine all of the edges with tail in X and head outside of X. One 214 00:15:37,691 --> 00:15:42,837 of those is gonna lead us to the vertex that we pick next. So that's the first 215 00:15:42,837 --> 00:15:46,359 idea, but now we need a second idea, because this is again quite 216 00:15:46,359 --> 00:15:50,775 under-determined. There could be multiple vertices, which meet this criterion. So 217 00:15:50,775 --> 00:15:55,303 for example in the cartoon in the bottom left part of this slide, you'll notice 218 00:15:55,303 --> 00:16:00,027 that there's one vertex here which is the head of an arc that crosses from left 219 00:16:00,027 --> 00:16:04,295 to right, and there is yet another vertex down here in V minus X, which again is the 220 00:16:04,295 --> 00:16:07,643 head of an arc that crosses from left to right. So there are two options, of which 221 00:16:07,643 --> 00:16:12,224 of those two to suck into our set X. And we might want some guidance about which 222 00:16:12,224 --> 00:16:17,059 one to pick next. So the key idea in Dijkstra is to give each vertex a score 223 00:16:17,059 --> 00:16:22,131 corresponding to how close that vertex seems to the source vertex S, and then to 224 00:16:22,131 --> 00:16:28,891 pick among all candidate vertices the one that has the minimum score. Lemme be more 225 00:16:28,891 --> 00:16:34,383 precise. So among all crossing edges, with tail on the left side and head on the 226 00:16:34,383 --> 00:16:41,584 right side, we pick the edge that minimizes the following criterion, the shortest path 227 00:16:41,584 --> 00:16:48,532 distance, that we previously computed from S to the vertex V, plus the length of the 228 00:16:48,532 --> 00:16:54,978 edge that connects V to W. So this is quite an important expression, so I will 229 00:16:54,978 --> 00:17:01,089 call this Dijkstra's greedy criterion. This is a very good idea to use this 230 00:17:01,089 --> 00:17:07,887 method to choose which vertex to add to the set X, as we'll see. I need to give a name 231 00:17:07,887 --> 00:17:13,669 to this edge which minimizes this quantity over all crossing edges. So let's call it 232 00:17:13,669 --> 00:17:19,465 V star W star. So for example in the cartoon in the bottom left maybe of the two edges 233 00:17:19,465 --> 00:17:24,299 crossing from left to right, maybe the top one is the one that has a smaller value, 234 00:17:24,299 --> 00:17:29,075 of Dijkstra's Greedy Criterion. So in that case this would be the vertex V star, and 235 00:17:29,075 --> 00:17:33,919 the other end of the edge would be the vertex W star. So this edge, V star W star 236 00:17:33,919 --> 00:17:38,264 is going to do wonders for us. It will both guide us to the vertex that we should 237 00:17:38,264 --> 00:17:41,652 add to X next. That's gonna be W star. It's going to tell us how we should 238 00:17:41,652 --> 00:17:46,781 compute the shortest path distance to W star as well as what the actual shortest 239 00:17:46,781 --> 00:17:51,604 path from X to W star is. So specifically in this iteration of the while loop, after 240 00:17:51,604 --> 00:17:59,275 we've chosen this edge V star W star, we add W star to X. Remember by definition W 241 00:17:59,275 --> 00:18:04,382 star was previously not in capital X. So we're making progress by adding it to X. 242 00:18:04,382 --> 00:18:08,831 That's one more vertex in X. Now, X is supposed to represent all of the nodes 243 00:18:08,831 --> 00:18:13,323 we've already processed. So an invariant of this algorithm is that we've computed 244 00:18:13,323 --> 00:18:17,233 shortest path distances for everybody in X as well as the actual shortest paths, so 245 00:18:17,233 --> 00:18:21,063 now that we're putting W star in X, we're responsible for all of this information, 246 00:18:21,063 --> 00:18:27,020 shortest path information. So what we're gonna do is we're gonna set the, our estimate 247 00:18:27,020 --> 00:18:33,503 of W star's shortest path distance from S to be equal to the value of this Dijkstra 248 00:18:33,503 --> 00:18:39,555 greedy criterion for this edge. That is, whatever our previously computed shortest-path 249 00:18:39,555 --> 00:18:46,008 distance from S to V star was, plus the length of the direct edge from V star to W star. Now 250 00:18:46,008 --> 00:18:52,260 a key point is to realize this code does make sense, by which I mean, if you think 251 00:18:52,260 --> 00:18:57,787 about this quantity, AV, this has been previously computed. And that's because 252 00:18:57,787 --> 00:19:02,083 an invariant of this algorithm is we've always computed shortest path distances to 253 00:19:02,083 --> 00:19:06,699 everything that's in X. And of course, the same thing holds when we need to assign W 254 00:19:06,699 --> 00:19:11,723 star its shortest path distance because V star was a member of X, we'd already computed 255 00:19:11,723 --> 00:19:16,358 its shortest path distance so we can just look up the V star entry position in 256 00:19:16,358 --> 00:19:20,458 the array A. So over on our picture on our left we would just say, well what did we 257 00:19:20,458 --> 00:19:23,890 compute the shortest path distance to V star previously? Maybe it's something like 258 00:19:23,890 --> 00:19:27,893 seventeen. And then we'd say you know, what is the length of this direct edge 259 00:19:27,893 --> 00:19:31,674 from V Star to W Star? Maybe that's six. Then we would just add seventeen and 260 00:19:31,674 --> 00:19:35,997 six, and we would put 23 as our estimate of the shortest path distance from S To W 261 00:19:35,997 --> 00:19:41,495 star. So we something analogous with the shortest paths itself and the array B. That 262 00:19:41,495 --> 00:19:46,545 is again we are responsible since we just added W star to capital X we're 263 00:19:46,545 --> 00:19:51,937 responsible for suggesting a path from S to W star in the B array. So what we're 264 00:19:51,937 --> 00:19:57,534 gonna do is we're just going to inherit the previously computed path to V star and 265 00:19:57,534 --> 00:20:03,089 were just gonna tack on the end one extra hop, namely the direct edge from V star to W star. 266 00:20:03,089 --> 00:20:08,658 That'll give us a path from S all the way to W star via V star as an intermediate pit 267 00:20:08,658 --> 00:20:12,403 stop. And that is the entirety of Dijkstra's algorithm. I have explained all 268 00:20:12,403 --> 00:20:16,537 of the ingredients about how it works at a conceptual level. So the two things that I 269 00:20:16,537 --> 00:20:20,232 owe you is, you know, why is it correct, why does it actually compute shortest 270 00:20:20,232 --> 00:20:23,830 paths directly to all the different vertices, and secondly, how fast can we 271 00:20:23,830 --> 00:20:27,575 implement it. The next two videos are going to answer both of those questions. 272 00:20:27,575 --> 00:20:31,708 But before we do that, let's go through an example to get a better feel of how this algorithm 273 00:20:31,708 --> 00:20:35,268 actually works. And I also wanna go through a non-example so that you can 274 00:20:35,268 --> 00:20:39,306 appreciate how it breaks down when there are negative edges and that will make it 275 00:20:39,306 --> 00:20:42,705 clear why we do need a proof of correctness. Because it's not correct 276 00:20:42,705 --> 00:20:45,020 without any assumptions about the edge lengths.