1 00:00:01,890 --> 00:00:04,930 - [Instructor] Hi there, we're going to continue 2 00:00:04,930 --> 00:00:08,553 our exploration of graphs and graph algorithms. 3 00:00:09,700 --> 00:00:12,453 And today we're going to do Shortest Paths. 4 00:00:14,310 --> 00:00:19,060 Now, Shortest Path is as you might expect 5 00:00:19,060 --> 00:00:24,060 the shortest path between two nodes in a graph. 6 00:00:24,290 --> 00:00:27,680 So if I've got node A and node B 7 00:00:27,680 --> 00:00:31,420 there may be multiple paths through the graph 8 00:00:32,450 --> 00:00:34,120 to get from node A to node B 9 00:00:34,120 --> 00:00:36,583 and we want to find the shortest one. 10 00:00:37,560 --> 00:00:41,740 And this has a lot of applications as you might expect. 11 00:00:41,740 --> 00:00:45,013 Virtually any problem that we can represent with a graph, 12 00:00:45,940 --> 00:00:48,860 shortest path is going to be helpful to us. 13 00:00:48,860 --> 00:00:51,141 Some examples are vehicle routing, 14 00:00:51,141 --> 00:00:54,228 network design, telecommunications, 15 00:00:54,228 --> 00:00:58,207 and there's a substantial class of optimization problems 16 00:00:58,207 --> 00:01:00,240 which we can represent as graphs 17 00:01:00,240 --> 00:01:03,053 and shortest path is a part of the solution. 18 00:01:04,500 --> 00:01:07,510 Now, of course, the canonical example 19 00:01:07,510 --> 00:01:10,470 is maps of cities and distances between them. 20 00:01:10,470 --> 00:01:15,470 So here we have a map of a portion of Southeast Nigeria 21 00:01:15,560 --> 00:01:19,590 and we can identify cities in this map 22 00:01:19,590 --> 00:01:21,460 that are connected by highways 23 00:01:22,400 --> 00:01:25,830 and we can abstract the highways as edges 24 00:01:25,830 --> 00:01:27,890 and assign weights to them 25 00:01:27,890 --> 00:01:31,060 that correspond to the distances between the cities. 26 00:01:31,060 --> 00:01:34,373 And so we have this abstract graph now. 27 00:01:35,360 --> 00:01:38,910 And it's perfectly natural to ask questions of this graph. 28 00:01:38,910 --> 00:01:41,240 For example, what's the shortest route 29 00:01:41,240 --> 00:01:43,970 from Benin city to Calabar? 30 00:01:43,970 --> 00:01:47,970 Or what's the shortest route from Ogoja to port Harcourt? 31 00:01:47,970 --> 00:01:49,880 Is it through Ugep or Otu? 32 00:01:49,880 --> 00:01:52,140 I don't know. I've never been to Nigeria. 33 00:01:52,140 --> 00:01:54,280 Or is it through Owerri? 34 00:01:54,280 --> 00:01:56,940 Are these are perfectly reasonable questions to ask? 35 00:01:56,940 --> 00:01:59,080 And so finding the shortest path 36 00:01:59,080 --> 00:02:01,723 is a natural kind of a problem. 37 00:02:03,850 --> 00:02:05,710 And we can look at this two ways. 38 00:02:05,710 --> 00:02:08,770 We can calculate the shortest paths 39 00:02:08,770 --> 00:02:10,760 from some node call it V knot 40 00:02:10,760 --> 00:02:13,820 to all other nodes in the graph 41 00:02:13,820 --> 00:02:17,740 or we can have some target node that we want to reach 42 00:02:17,740 --> 00:02:20,340 and we calculate the shortest path 43 00:02:20,340 --> 00:02:23,993 from node V knot to this other node, call it V1. 44 00:02:24,850 --> 00:02:26,880 And obviously if we've solved the first, 45 00:02:26,880 --> 00:02:28,160 then we've solved the second. 46 00:02:28,160 --> 00:02:30,350 So we're going to focus on the approach 47 00:02:30,350 --> 00:02:32,080 where we solve the first 48 00:02:32,080 --> 00:02:36,103 we find the shortest paths to all other nodes in the graph. 49 00:02:37,950 --> 00:02:40,850 Now, let's take a look at this graph here. 50 00:02:40,850 --> 00:02:45,270 Here we have a undirected unweighted graph 51 00:02:45,270 --> 00:02:48,513 and we have node A colored here. 52 00:02:49,430 --> 00:02:51,993 And in this case, 53 00:02:53,260 --> 00:02:58,260 if we wanted to calculate the shortest path, 54 00:02:58,420 --> 00:03:02,220 we would calculate the minimum number of steps that it takes 55 00:03:02,220 --> 00:03:06,473 to get from no day to any other node in the graph. 56 00:03:07,440 --> 00:03:10,600 We just count the edges that we'd have to traverse. 57 00:03:10,600 --> 00:03:13,220 So we'd come up with something like this. 58 00:03:13,220 --> 00:03:14,950 Yeah, there are longer paths 59 00:03:14,950 --> 00:03:18,500 like I can find a path to J from A 60 00:03:18,500 --> 00:03:20,690 that goes through B and H 61 00:03:20,690 --> 00:03:23,520 that would have a length one, two, three 62 00:03:24,370 --> 00:03:27,900 but this one's shorter just one step. 63 00:03:27,900 --> 00:03:30,930 So this would be the solutions to shortest paths 64 00:03:30,930 --> 00:03:33,833 in an undirected unweighted graph. 65 00:03:34,930 --> 00:03:37,290 And the problem would be the same 66 00:03:37,290 --> 00:03:39,260 if we had a way to graph, 67 00:03:39,260 --> 00:03:42,210 if all the weights were equal to one, 68 00:03:42,210 --> 00:03:43,943 we'd get exactly the same numbers. 69 00:03:45,810 --> 00:03:49,700 And we could even generalize this further 70 00:03:49,700 --> 00:03:51,720 to a directed graph. 71 00:03:51,720 --> 00:03:55,110 Here, it's exactly the same graph 72 00:03:55,110 --> 00:03:57,510 essentially as the one we saw here, 73 00:03:57,510 --> 00:04:00,580 except we've represented the undirected edges 74 00:04:00,580 --> 00:04:03,250 as two directed edges both at the same way, 75 00:04:03,250 --> 00:04:05,140 all the way it's here one. 76 00:04:05,140 --> 00:04:07,120 And so we'd come up with the same values 77 00:04:07,120 --> 00:04:08,532 for the shortest path. 78 00:04:08,532 --> 00:04:12,030 So the shortest path between A and B is of length one, 79 00:04:12,030 --> 00:04:15,880 the shortest path between B and D is of link three, 80 00:04:15,880 --> 00:04:18,380 the shortest path between A and H 81 00:04:18,380 --> 00:04:19,973 is of length two and so on. 82 00:04:23,820 --> 00:04:25,860 So let's look at a little simpler problem 83 00:04:25,860 --> 00:04:28,130 without quite all that clutter. 84 00:04:28,130 --> 00:04:30,480 So I've removed some edges here 85 00:04:30,480 --> 00:04:34,830 and we still have a directed graph 86 00:04:35,690 --> 00:04:37,590 and all the edge weights are the same. 87 00:04:38,440 --> 00:04:40,270 And if we were to calculate again, 88 00:04:40,270 --> 00:04:43,063 we'd wind up with the same distances. 89 00:04:44,670 --> 00:04:47,470 But what if the edge weights were different? 90 00:04:47,470 --> 00:04:48,770 If the edge weights were different 91 00:04:48,770 --> 00:04:50,970 we'd have a little more complicated problem. 92 00:04:52,230 --> 00:04:54,680 And here the distance of a given path 93 00:04:54,680 --> 00:04:58,230 is the sum of the weights of the edges in the path. 94 00:04:58,230 --> 00:05:01,370 So for example, this path 95 00:05:01,370 --> 00:05:06,300 going from A to B to H has length 10, 96 00:05:06,300 --> 00:05:09,230 the distance between A and H we say is 10, 97 00:05:09,230 --> 00:05:10,860 because this one is seven, 98 00:05:10,860 --> 00:05:13,043 this one is three, seven plus three is 10. 99 00:05:14,840 --> 00:05:17,860 This path has a length of 25, 100 00:05:17,860 --> 00:05:22,500 six plus one is seven, plus seven is 14 plus 11 is 25. 101 00:05:22,500 --> 00:05:27,150 So this particular path from A to F 102 00:05:27,150 --> 00:05:29,903 has a distance of 25. 103 00:05:30,890 --> 00:05:33,910 And where we could quickly arrive at a solution 104 00:05:33,910 --> 00:05:35,920 by a visual inspection of the graph 105 00:05:35,920 --> 00:05:38,210 given these small problem instances 106 00:05:38,210 --> 00:05:40,220 already it's not as easy to say, 107 00:05:40,220 --> 00:05:42,050 what are all the shortest paths 108 00:05:42,050 --> 00:05:45,850 between A and all the other nodes in this graph. 109 00:05:45,850 --> 00:05:48,180 So even with a small problem instance 110 00:05:48,180 --> 00:05:49,980 it starts to become pretty cumbersome. 111 00:05:49,980 --> 00:05:52,296 And you can imagine the graph I showed you earlier 112 00:05:52,296 --> 00:05:56,320 of the cities and highways in Nigeria, 113 00:05:56,320 --> 00:05:57,700 that's even more complicated 114 00:05:57,700 --> 00:06:00,850 and that too is a small problem instance. 115 00:06:00,850 --> 00:06:03,400 So we need an algorithm that will work 116 00:06:03,400 --> 00:06:05,740 on graphs of any size. 117 00:06:05,740 --> 00:06:08,703 So allow me to introduce Edgar Dijkstra. 118 00:06:09,860 --> 00:06:14,240 Back in the 1950s, Dutch computer scientist, Edgar Dijkstra 119 00:06:14,240 --> 00:06:16,990 came up with an algorithm that we'll present here. 120 00:06:16,990 --> 00:06:19,660 It's an example of a greedy algorithm. 121 00:06:19,660 --> 00:06:21,640 We'll see what that means in a little bit. 122 00:06:21,640 --> 00:06:24,940 And it solves the problem of finding the shortest path 123 00:06:24,940 --> 00:06:28,010 in a graph between some node, 124 00:06:28,010 --> 00:06:30,610 call it again call it V node or A 125 00:06:30,610 --> 00:06:33,670 to all the other nodes in the graph. 126 00:06:33,670 --> 00:06:37,050 And the story goes that Dijkstra 127 00:06:37,050 --> 00:06:39,390 came up with this while he was sipping coffee 128 00:06:39,390 --> 00:06:43,090 in a cafe someplace, he didn't have pencil or paper, 129 00:06:43,090 --> 00:06:46,540 he just arranged things on the tabletop 130 00:06:46,540 --> 00:06:48,823 and worked out a solution. 131 00:06:49,660 --> 00:06:51,380 Three years later, he published it 132 00:06:51,380 --> 00:06:53,560 and now it's one of the most famous algorithms 133 00:06:53,560 --> 00:06:55,480 on the planet, Dijkstra's algorithm. 134 00:06:55,480 --> 00:06:56,833 So that's Edgar Dijkstra. 135 00:06:58,010 --> 00:07:01,920 Who's a bit of a character to, Google some of his quotes. 136 00:07:01,920 --> 00:07:04,313 He's a very opinionated person. 137 00:07:06,630 --> 00:07:10,060 So, how does Dijkstra algorithm work? 138 00:07:10,060 --> 00:07:13,260 Well, let's say we wanted to find the shortest path 139 00:07:13,260 --> 00:07:16,513 between node A and all the other nodes in this graph. 140 00:07:17,410 --> 00:07:21,100 So we start by creating a set of unvisited notes 141 00:07:21,100 --> 00:07:23,500 and initially that will be the same 142 00:07:23,500 --> 00:07:25,750 as the node set for the entire graph. 143 00:07:25,750 --> 00:07:30,510 So A, B, C, D, F, H, J, K and L that's all the notes here. 144 00:07:30,510 --> 00:07:33,410 So we mark all the nodes as unvisited. 145 00:07:33,410 --> 00:07:36,520 Then the next thing we do to initialize our problem 146 00:07:36,520 --> 00:07:40,050 is we assign a distance of zero to our starting node 147 00:07:40,050 --> 00:07:44,660 and a distance of infinity to all other nodes, okay? 148 00:07:44,660 --> 00:07:47,380 And if our programming language doesn't have 149 00:07:48,453 --> 00:07:52,580 infinity, then we just use an extremely large number 150 00:07:52,580 --> 00:07:55,783 some number that we don't expect to encounter in our graph. 151 00:08:01,100 --> 00:08:03,550 And then we start with the unvisited node. 152 00:08:03,550 --> 00:08:06,343 That's the node with the smallest distance, right? 153 00:08:07,510 --> 00:08:09,948 Node A has distance zero 154 00:08:09,948 --> 00:08:12,440 and all the other nodes have distance infinity. 155 00:08:12,440 --> 00:08:15,970 So we start with A and we calculate the distance 156 00:08:15,970 --> 00:08:19,260 to all unvisited neighbors of A. 157 00:08:19,260 --> 00:08:21,890 So in this case that's B and J 158 00:08:21,890 --> 00:08:23,990 and we compare the calculated distance 159 00:08:23,990 --> 00:08:25,800 with the current distance. 160 00:08:25,800 --> 00:08:28,190 Now, the current distance are both infinity. 161 00:08:28,190 --> 00:08:30,900 So when we calculate the distances, 162 00:08:30,900 --> 00:08:34,150 we're going to set the distance to B, to be seven. 163 00:08:34,150 --> 00:08:35,720 Seven is less than infinity. 164 00:08:35,720 --> 00:08:38,893 So we're gonna update this to be seven. 165 00:08:40,150 --> 00:08:44,564 And then we're gonna calculate the distance to J, 166 00:08:44,564 --> 00:08:47,260 we're gonna set that equal to six. 167 00:08:47,260 --> 00:08:50,780 And we're also gonna make a note of where we came from. 168 00:08:50,780 --> 00:08:55,200 when we updated these distances. 169 00:08:55,200 --> 00:08:57,340 We came from node A to get to B, 170 00:08:57,340 --> 00:08:59,380 we came from node A to get to J, 171 00:08:59,380 --> 00:09:02,170 so we update these it's gonna look like this. 172 00:09:02,170 --> 00:09:07,170 The distance so far from A to B is seven. 173 00:09:07,510 --> 00:09:11,290 We came from A the distance from A to J is six 174 00:09:11,290 --> 00:09:13,213 we came from A, okay? 175 00:09:14,820 --> 00:09:17,030 So what do we do now? 176 00:09:17,030 --> 00:09:18,400 We mark A is visited. 177 00:09:18,400 --> 00:09:20,083 We take it out of this set, 178 00:09:21,520 --> 00:09:22,830 mark it as visited. 179 00:09:22,830 --> 00:09:26,420 And now we want to find the next node 180 00:09:26,420 --> 00:09:29,480 from which we're going to continue our exploration. 181 00:09:29,480 --> 00:09:31,250 And we choose the next node 182 00:09:31,250 --> 00:09:33,170 based on the shortest distance again. 183 00:09:33,170 --> 00:09:36,560 So we've already visited A that's off the list. 184 00:09:36,560 --> 00:09:39,610 So of all these remaining nodes 185 00:09:39,610 --> 00:09:44,610 that are so far unvisited J has the smallest distance. 186 00:09:45,470 --> 00:09:48,003 So we're gonna explore from J. 187 00:09:50,290 --> 00:09:51,730 So we're gonna explore from J 188 00:09:51,730 --> 00:09:54,223 we're gonna calculate the distances from J. 189 00:09:55,240 --> 00:09:58,110 It turns out that we can only reach one node from J 190 00:09:58,110 --> 00:10:00,450 that's H along this edge. 191 00:10:00,450 --> 00:10:03,583 The edge connecting J and H has weight five, 192 00:10:03,583 --> 00:10:07,680 and the distance to J we've already seen is six. 193 00:10:07,680 --> 00:10:12,200 And so we're gonna calculate the distance to H as 11 194 00:10:12,200 --> 00:10:15,323 but we're gonna make a note that we arrive there from J. 195 00:10:16,380 --> 00:10:19,080 So there's our values for H. 196 00:10:19,080 --> 00:10:22,820 The distance is 11 and we arrive there from J. 197 00:10:22,820 --> 00:10:23,763 So far so good. 198 00:10:25,400 --> 00:10:27,340 So let's mark J as visited 199 00:10:27,340 --> 00:10:30,140 by removing it from the old visited set. 200 00:10:30,140 --> 00:10:34,150 And then we're gonna find the next node to explore. 201 00:10:34,150 --> 00:10:37,510 Now of all of the unvisited nodes, 202 00:10:37,510 --> 00:10:39,620 the one with the smallest value is B 203 00:10:39,620 --> 00:10:41,583 that's seven so we choose B. 204 00:10:43,330 --> 00:10:47,623 Now from B, we can reach C and we can reach H. 205 00:10:49,240 --> 00:10:52,780 Now the edge connecting B and C has weight nine, 206 00:10:52,780 --> 00:10:55,340 B has a distance of seven from A 207 00:10:55,340 --> 00:10:57,290 so the distance from A to C 208 00:10:57,290 --> 00:10:59,515 that we're gonna calculate through this route 209 00:10:59,515 --> 00:11:01,375 is going to be 16. 210 00:11:01,375 --> 00:11:03,373 16 is less than infinity 211 00:11:03,373 --> 00:11:08,373 and so we're gonna update the distance to C 212 00:11:08,610 --> 00:11:13,610 and we're gonna note that we arrived at C from B, okay? 213 00:11:13,690 --> 00:11:16,270 Now we have this edge to consider. 214 00:11:16,270 --> 00:11:19,390 We can also get from B to H. 215 00:11:19,390 --> 00:11:22,940 And notice that this has a weight of three 216 00:11:22,940 --> 00:11:24,610 and the distance here is seven. 217 00:11:24,610 --> 00:11:28,830 So we calculate the distance to H has 10. 218 00:11:28,830 --> 00:11:32,933 Now 10 is less than the current distance, which is 11. 219 00:11:33,774 --> 00:11:36,640 And so we found a shorter route to H. 220 00:11:36,640 --> 00:11:40,970 The route through J has distance 11 221 00:11:40,970 --> 00:11:44,183 but the route through B has distance 10. 222 00:11:45,130 --> 00:11:49,310 So we're gonna update the values for H 223 00:11:49,310 --> 00:11:53,220 to show that the distance is now 10 it's reduced by one. 224 00:11:53,220 --> 00:11:55,450 And now we arrived at H from B. 225 00:11:55,450 --> 00:11:58,300 We only concern ourselves with where we arrive from 226 00:11:58,300 --> 00:12:00,600 for the shortest path that we've found so far. 227 00:12:02,330 --> 00:12:05,280 So that finishes things for B. 228 00:12:05,280 --> 00:12:06,710 We mark B as visited. 229 00:12:06,710 --> 00:12:09,490 We remove it from the unvisited set 230 00:12:09,490 --> 00:12:13,003 and now we hunt for the next node to work from. 231 00:12:14,270 --> 00:12:17,810 And of the remaining nodes, H has the lowest value. 232 00:12:17,810 --> 00:12:20,720 So we're gonna explore from H. 233 00:12:20,720 --> 00:12:25,448 And from H we can only reach L by this edge of weight two. 234 00:12:25,448 --> 00:12:29,760 The distance here is 10, that's going this way. 235 00:12:29,760 --> 00:12:34,070 And so we're gonna calculate the distance L is 12, 236 00:12:34,070 --> 00:12:36,330 12 is less than infinity. 237 00:12:36,330 --> 00:12:39,840 And so we're going to set the value for L to be 12. 238 00:12:39,840 --> 00:12:44,300 And we're gonna indicate that we arrived there from node H. 239 00:12:44,300 --> 00:12:46,128 We're going to mark H as visited 240 00:12:46,128 --> 00:12:49,800 and now we're going to find the next node to explore. 241 00:12:49,800 --> 00:12:53,143 The next node is L which has the lowest value, 12. 242 00:12:54,400 --> 00:12:58,220 And so we explore from L and we calculate the distances. 243 00:12:58,220 --> 00:13:01,090 The only thing we can reach from, well, actually no 244 00:13:01,090 --> 00:13:02,710 we have two things we can reach from L. 245 00:13:02,710 --> 00:13:05,350 We can reach K and we can reach F. 246 00:13:05,350 --> 00:13:07,890 So let's consider this one first. 247 00:13:07,890 --> 00:13:12,380 So we have 12 here plus three equals 15, 248 00:13:12,380 --> 00:13:14,900 15 is less than infinity. 249 00:13:14,900 --> 00:13:19,900 So we're gonna update K to say that the distance is 15 250 00:13:19,960 --> 00:13:22,415 and that we arrive there from node L. 251 00:13:22,415 --> 00:13:27,260 And now let's consider this edge here that gets us to F 252 00:13:27,260 --> 00:13:29,973 that's 12 plus one is 13. 253 00:13:29,973 --> 00:13:31,550 13 is less than infinity. 254 00:13:31,550 --> 00:13:33,570 So we're going to update that 255 00:13:33,570 --> 00:13:37,100 and indicate that we arrived by the current shortest path 256 00:13:37,100 --> 00:13:39,483 of 13 from node L. 257 00:13:41,230 --> 00:13:42,880 We're gonna mark L as visited 258 00:13:44,610 --> 00:13:46,310 and now we're gonna choose the next node 259 00:13:46,310 --> 00:13:47,680 from which to explore. 260 00:13:47,680 --> 00:13:50,930 The next node from which to explore is going to be F 261 00:13:50,930 --> 00:13:52,840 because F has the smallest value 262 00:13:52,840 --> 00:13:56,083 of the remaining vertices that are in our unvisited set. 263 00:13:57,510 --> 00:14:00,800 So we start from F we calculate some distances. 264 00:14:00,800 --> 00:14:05,050 The only thing we can reach is D by this edge. 265 00:14:05,050 --> 00:14:09,630 So we have 13 plus seven gives us 20, 266 00:14:09,630 --> 00:14:11,680 20 is less than infinity. 267 00:14:11,680 --> 00:14:13,940 So we set this to be 20 268 00:14:13,940 --> 00:14:16,373 and indicate that we arrived here from F. 269 00:14:17,800 --> 00:14:21,350 And that's it for F so we mark F as visited 270 00:14:21,350 --> 00:14:24,907 and now we just have CD and K in our unvisited set. 271 00:14:24,907 --> 00:14:29,290 That's the one with the smallest value is K. 272 00:14:29,290 --> 00:14:32,010 So we're gonna visit K 273 00:14:32,010 --> 00:14:34,370 and we're gonna find its neighbors. 274 00:14:34,370 --> 00:14:37,300 But we noticed that all of K's neighbors 275 00:14:37,300 --> 00:14:38,410 have already been visited. 276 00:14:38,410 --> 00:14:40,090 The only one we can reach is J 277 00:14:40,090 --> 00:14:41,870 but we've already marked J as visited. 278 00:14:41,870 --> 00:14:44,740 So there's nothing for us to do. 279 00:14:44,740 --> 00:14:47,246 So we're just gonna mark K is visited 280 00:14:47,246 --> 00:14:49,373 and remove it from set U. 281 00:14:50,240 --> 00:14:52,050 So now what's next. 282 00:14:52,050 --> 00:14:56,440 We have C and D left. C has a distance of 16. 283 00:14:56,440 --> 00:14:58,453 So we'll explore from C. 284 00:15:01,210 --> 00:15:04,040 From C we can only reach node D 285 00:15:04,040 --> 00:15:06,600 but we do it along this edge, which has weight two. 286 00:15:06,600 --> 00:15:09,547 So 16 plus two gives us 18. 287 00:15:09,547 --> 00:15:13,000 18 is less than 20. 288 00:15:13,000 --> 00:15:15,970 So we're going to update the value for D. 289 00:15:15,970 --> 00:15:17,882 So the distance is 18 290 00:15:17,882 --> 00:15:22,143 and indicate that we arrived at D from node C. 291 00:15:23,160 --> 00:15:25,023 We're gonna mark C as visited. 292 00:15:25,910 --> 00:15:28,100 Then the only thing left to pick is D. 293 00:15:28,100 --> 00:15:31,000 So we're gonna explore from D and calculate the distances, 294 00:15:31,000 --> 00:15:33,577 but of course all the other nodes were already visited. 295 00:15:33,577 --> 00:15:36,320 So there's nothing for us to do. 296 00:15:36,320 --> 00:15:40,890 We marked is visited and we're done. 297 00:15:40,890 --> 00:15:43,190 The unvisited set is empty. 298 00:15:43,190 --> 00:15:44,720 All the nodes have been visited 299 00:15:44,720 --> 00:15:46,750 and now we know the shortest path 300 00:15:46,750 --> 00:15:49,360 from A to any node in the graph. 301 00:15:49,360 --> 00:15:50,590 They're are all shown here. 302 00:15:50,590 --> 00:15:52,860 These are all the shortest distances. 303 00:15:52,860 --> 00:15:54,560 And the distances are obvious 304 00:15:54,560 --> 00:15:57,100 but how do we know the shortest paths? 305 00:15:57,100 --> 00:16:01,470 Well, we kept track of the node that we arrived from 306 00:16:01,470 --> 00:16:04,180 whenever we found a shortest path. 307 00:16:04,180 --> 00:16:09,180 So we can use this information to recover any shortest path. 308 00:16:09,400 --> 00:16:13,530 So, for example, what's the shortest path from A to L? 309 00:16:13,530 --> 00:16:15,660 We know what's of length 12. 310 00:16:15,660 --> 00:16:20,477 So let's start at L and work our way backward, right? 311 00:16:21,720 --> 00:16:25,483 This tells us that we arrived at L from H. 312 00:16:27,020 --> 00:16:32,020 So we know this edge is on the shortest path. 313 00:16:32,160 --> 00:16:34,150 And now how did we get to H? 314 00:16:34,150 --> 00:16:37,023 By the shortest path, we arrived from B. 315 00:16:37,880 --> 00:16:42,430 So this edge is going to be along the shortest path. 316 00:16:42,430 --> 00:16:46,010 And how did we get to B from A? 317 00:16:46,010 --> 00:16:49,690 And so that edge is gonna be on the shortest path. 318 00:16:49,690 --> 00:16:54,180 And so now we've reconstructed the shortest path from A to L 319 00:16:55,200 --> 00:16:59,620 by working backwards from our partial solutions. 320 00:16:59,620 --> 00:17:02,740 This is a technique that's called dynamic programming 321 00:17:02,740 --> 00:17:05,520 where we save partial solutions as we go, 322 00:17:05,520 --> 00:17:09,470 each of these notations of where we came from 323 00:17:09,470 --> 00:17:12,390 when we arrived at the new shortest path, 324 00:17:12,390 --> 00:17:14,385 those are all partial solutions. 325 00:17:14,385 --> 00:17:17,170 And we use these partial solutions 326 00:17:17,170 --> 00:17:21,080 to reconstruct the shortest path between A and L. 327 00:17:21,080 --> 00:17:22,550 And obviously we can do that 328 00:17:22,550 --> 00:17:26,720 between any node in the graph and A. 329 00:17:26,720 --> 00:17:29,010 So the partial solutions 330 00:17:29,010 --> 00:17:31,430 are used to reconstruct a complete solution. 331 00:17:31,430 --> 00:17:33,330 This is called dynamic programming. 332 00:17:33,330 --> 00:17:37,370 If you see it in other classes like CS224, 333 00:17:37,370 --> 00:17:39,167 they'll make a big deal about it. 334 00:17:39,167 --> 00:17:42,830 Dynamic programming sounds like a very daunting thing 335 00:17:42,830 --> 00:17:45,040 but it's really very simple concept. 336 00:17:45,040 --> 00:17:49,040 You save your work as you go in partial solutions 337 00:17:49,040 --> 00:17:51,110 and use those partial solutions 338 00:17:51,110 --> 00:17:54,440 to reconstruct a complete solution. 339 00:17:54,440 --> 00:17:56,823 when you're done processing your problem. 340 00:17:56,823 --> 00:17:58,503 That's all there is to it. 341 00:17:59,520 --> 00:18:02,490 Again, we can do this for any pair of nodes 342 00:18:02,490 --> 00:18:05,480 once we've processed the graph. 343 00:18:05,480 --> 00:18:07,453 So that's Dijkstra's algorithm. 344 00:18:08,810 --> 00:18:11,380 And we could pick any starting node in this graph. 345 00:18:11,380 --> 00:18:14,100 We could choose B and run the whole algorithm 346 00:18:14,100 --> 00:18:17,870 again or choose K or choose F, it doesn't matter. 347 00:18:17,870 --> 00:18:21,300 And we'll come up with a different set of distances, 348 00:18:21,300 --> 00:18:24,635 but in each case, we'll find the shortest path 349 00:18:24,635 --> 00:18:28,620 that exists between some starting point in the graph 350 00:18:28,620 --> 00:18:30,470 and all the other nodes in the graph. 351 00:18:31,880 --> 00:18:35,733 What did you notice about how we chose the nodes to visit? 352 00:18:37,860 --> 00:18:42,053 Well, we always chose the node with the smallest distance. 353 00:18:43,900 --> 00:18:46,750 Now, can you think of a data structure 354 00:18:46,750 --> 00:18:50,203 that's handy for always extracting the smallest value? 355 00:18:51,882 --> 00:18:54,282 The answer should be, yes we've seen one already 356 00:18:56,660 --> 00:18:58,393 a minimum priority queue. 357 00:18:59,270 --> 00:19:02,540 And it turns out that we commonly implement 358 00:19:02,540 --> 00:19:06,240 Dijkstra's algorithm using a minimum priority queue. 359 00:19:06,240 --> 00:19:08,240 So let's take a look at some pseudocode. 360 00:19:09,580 --> 00:19:11,860 So here's some pseudocode we've got this function, 361 00:19:11,860 --> 00:19:15,840 Dijkstra it takes G and S as parameters. 362 00:19:15,840 --> 00:19:20,050 G is the graph and S is the starting node. 363 00:19:20,050 --> 00:19:23,660 And then for each node V in the graph, 364 00:19:23,660 --> 00:19:27,200 we have this vector or a array 365 00:19:27,200 --> 00:19:29,650 that stores where we arrived from. 366 00:19:29,650 --> 00:19:32,300 Those are the notations of where we arrived from 367 00:19:32,300 --> 00:19:35,850 to get to our partial solution. 368 00:19:35,850 --> 00:19:38,730 And so we set those all to null. 369 00:19:38,730 --> 00:19:40,923 If V is the starting node, 370 00:19:40,923 --> 00:19:44,630 then we set the distance to V equal to zero. 371 00:19:44,630 --> 00:19:49,010 Otherwise we set all the other distances to be infinite 372 00:19:49,010 --> 00:19:53,280 and we add each node to the priority queue. 373 00:19:53,280 --> 00:19:56,170 And the priority queue is a minimum queue. 374 00:19:56,170 --> 00:19:58,740 So the minimum value is going to be at the root 375 00:19:58,740 --> 00:20:00,480 once it's done all of its work 376 00:20:00,480 --> 00:20:03,513 to preserve the heat border property. 377 00:20:04,350 --> 00:20:07,660 And so we're ready to extract the minimum value. 378 00:20:07,660 --> 00:20:10,470 Now, in the first case, it's gonna be zero 379 00:20:10,470 --> 00:20:14,920 cause we've initialized the starting node to be zero 380 00:20:14,920 --> 00:20:16,360 and all the others to be infinite. 381 00:20:16,360 --> 00:20:21,270 So we know at the first iteration, zero is at the root. 382 00:20:21,270 --> 00:20:23,600 So we have this while loop, 383 00:20:23,600 --> 00:20:25,793 while the queue is not empty, 384 00:20:25,793 --> 00:20:28,800 we get the minimum value from the priority queue. 385 00:20:28,800 --> 00:20:30,460 We call that V. 386 00:20:30,460 --> 00:20:35,240 And then for each unvisited neighbor, N of V, 387 00:20:35,240 --> 00:20:37,050 we calculate that distance 388 00:20:37,050 --> 00:20:40,160 which is the distance that we've already found to V 389 00:20:40,160 --> 00:20:43,493 plus the distance to N along that new edge. 390 00:20:44,490 --> 00:20:46,910 And if that distance is less than 391 00:20:46,910 --> 00:20:50,033 what's already stored for that node, 392 00:20:50,880 --> 00:20:52,880 when we start out it's going to be infinite, 393 00:20:52,880 --> 00:20:54,620 but we'll update those as we go. 394 00:20:54,620 --> 00:20:56,980 Then that means we've found a shorter distance 395 00:20:56,980 --> 00:20:58,250 and we update it. 396 00:20:58,250 --> 00:21:00,370 So how do we do the update? 397 00:21:00,370 --> 00:21:04,440 We set the distance for that node to be the new distance 398 00:21:04,440 --> 00:21:05,645 that we just calculated. 399 00:21:05,645 --> 00:21:09,130 And we make a note of where we arrived from 400 00:21:09,130 --> 00:21:13,460 which was in this case V we arrived at node N from V. 401 00:21:13,460 --> 00:21:17,730 So this, my friends is a complete implementation 402 00:21:17,730 --> 00:21:19,490 of Dijkstra's algorithm. 403 00:21:19,490 --> 00:21:21,500 It is a very concise algorithm. 404 00:21:21,500 --> 00:21:23,323 It's a very, very elegant thing. 405 00:21:24,690 --> 00:21:28,960 So there's a catch. 406 00:21:28,960 --> 00:21:30,563 There's always a catch, right? 407 00:21:31,600 --> 00:21:33,470 What's the catch with Dijkstra's algorithm. 408 00:21:33,470 --> 00:21:36,260 It only works for directed graphs 409 00:21:36,260 --> 00:21:38,910 as long as all the weights are non-negative. 410 00:21:38,910 --> 00:21:42,923 You can have zeros, but you can't have negative values. 411 00:21:43,870 --> 00:21:46,833 And the idea is a simple one. 412 00:21:48,140 --> 00:21:52,100 Dijkstra's algorithm operates on the presumption 413 00:21:52,100 --> 00:21:56,440 that as we add edges to a path, 414 00:21:56,440 --> 00:21:59,960 we're never going to decrease the length of a path 415 00:21:59,960 --> 00:22:02,280 by adding an edge, okay? 416 00:22:02,280 --> 00:22:06,710 You have a monotonically non-decreasing function 417 00:22:06,710 --> 00:22:09,393 and that's a presumption of Dijkstra's algorithm. 418 00:22:11,070 --> 00:22:14,210 So Dijkstra's algorithm cannot handle negative weights. 419 00:22:14,210 --> 00:22:16,890 Now, of course, in the case of a map, 420 00:22:16,890 --> 00:22:19,680 you're not gonna have a negative distance 421 00:22:19,680 --> 00:22:21,810 from Detroit to Toledo. 422 00:22:21,810 --> 00:22:24,340 They're always going to be positive values 423 00:22:24,340 --> 00:22:25,982 but there are a lot of problems 424 00:22:25,982 --> 00:22:30,040 for which it's reasonable to use a negative weight 425 00:22:30,040 --> 00:22:31,470 along an edge. 426 00:22:31,470 --> 00:22:34,163 And for those Dijkstra's algorithm doesn't work. 427 00:22:36,160 --> 00:22:37,740 And what's the complexity. 428 00:22:37,740 --> 00:22:39,450 Well, the worst case complexity 429 00:22:39,450 --> 00:22:42,020 using a minimum priority queue, 430 00:22:42,020 --> 00:22:43,770 we have to go through all the vertices. 431 00:22:43,770 --> 00:22:45,490 We have to go through all the edges. 432 00:22:45,490 --> 00:22:50,490 So that's the cardinality V plus the cardinality V 433 00:22:50,750 --> 00:22:52,970 and we're using a priority queue. 434 00:22:52,970 --> 00:22:56,520 So we have log V term here, 435 00:22:56,520 --> 00:22:58,910 and this gives us the worst case complexity 436 00:22:58,910 --> 00:23:02,183 for Dijkstra's algorithm using a minimum priority queue. 437 00:23:03,150 --> 00:23:05,620 And as we've already noted, it's a greedy algorithm. 438 00:23:05,620 --> 00:23:08,630 It always chooses the best shortest distance 439 00:23:08,630 --> 00:23:11,173 that's been found so far, okay? 440 00:23:12,040 --> 00:23:15,088 What really does that mean, greedy approach? 441 00:23:15,088 --> 00:23:18,210 Like I said, we always choose the shortest distance 442 00:23:18,210 --> 00:23:19,780 we've calculated so far, 443 00:23:19,780 --> 00:23:22,810 but it's important to note that we never go back. 444 00:23:22,810 --> 00:23:25,450 Once a node is marked as visited, 445 00:23:25,450 --> 00:23:27,150 we never revisit it. 446 00:23:27,150 --> 00:23:30,790 So we grab the best result in a greedy way. 447 00:23:30,790 --> 00:23:33,791 And if we find a better one, we grab that. 448 00:23:33,791 --> 00:23:38,250 We never go back to a node once it's marked as visited. 449 00:23:38,250 --> 00:23:41,610 So as we go through the algorithm, 450 00:23:41,610 --> 00:23:44,170 we mark these nodes as visited 451 00:23:44,170 --> 00:23:45,790 and we never update them 452 00:23:45,790 --> 00:23:47,590 once they've been marked as visited. 453 00:23:48,980 --> 00:23:53,320 So now question, why doesn't Dijkstra's algorithm 454 00:23:53,320 --> 00:23:55,450 work with negative weights? 455 00:23:55,450 --> 00:23:57,383 Well, let's look at a simple example. 456 00:23:58,780 --> 00:24:01,040 Here we have a directed graph, 457 00:24:01,040 --> 00:24:03,620 weighted graph with a negative weight here 458 00:24:03,620 --> 00:24:06,440 you see there's a negative eight here, 459 00:24:06,440 --> 00:24:09,000 and let's just run Dijkstra's algorithm on it. 460 00:24:09,000 --> 00:24:10,566 We're starting from node A 461 00:24:10,566 --> 00:24:13,699 and what we're gonna do is we're gonna calculate 462 00:24:13,699 --> 00:24:16,980 the distance to all the unvisited neighbors of A 463 00:24:16,980 --> 00:24:19,433 which is B, C and D. 464 00:24:20,330 --> 00:24:24,660 And we're going to get seven and we arrived from A and five. 465 00:24:24,660 --> 00:24:26,220 We arrived from A and nine. 466 00:24:26,220 --> 00:24:28,700 We arrived from A, okay? 467 00:24:28,700 --> 00:24:32,723 Then we're going to mark A as having been visited, 468 00:24:32,723 --> 00:24:35,210 and we're gonna move on to B. 469 00:24:35,210 --> 00:24:37,773 Now, what happens when we look at B? 470 00:24:37,773 --> 00:24:42,773 Well, we're going to see that we can reach C from B 471 00:24:43,120 --> 00:24:47,440 but that's five plus five is 10 is greater than seven. 472 00:24:47,440 --> 00:24:49,070 So we're not gonna update here 473 00:24:49,070 --> 00:24:50,790 but we're going to mark B as visited. 474 00:24:50,790 --> 00:24:52,533 So now A and B are visited. 475 00:24:53,550 --> 00:24:55,940 And then we're gonna look at C 476 00:24:55,940 --> 00:24:59,580 and we're gonna see that C we can get to D 477 00:24:59,580 --> 00:25:02,000 but that gives us seven plus four is 11 478 00:25:02,000 --> 00:25:05,037 is greater than nine and so we don't update that. 479 00:25:05,037 --> 00:25:08,130 And so we mark C as visited. 480 00:25:08,130 --> 00:25:09,503 And now we get to D 481 00:25:09,503 --> 00:25:12,980 and we only look at the unvisited neighbors 482 00:25:12,980 --> 00:25:14,880 but there are no unvisited neighbors. 483 00:25:14,880 --> 00:25:16,610 And so we have nothing to do 484 00:25:16,610 --> 00:25:18,630 and then we're gonna mark D is visited 485 00:25:19,740 --> 00:25:22,660 but we got a problem here, all right? 486 00:25:22,660 --> 00:25:25,794 And the problem is, is that we didn't discover 487 00:25:25,794 --> 00:25:28,530 the real shortest paths. 488 00:25:28,530 --> 00:25:31,510 We followed the algorithm to the letter, 489 00:25:31,510 --> 00:25:33,290 but we didn't find the shortest paths. 490 00:25:33,290 --> 00:25:34,560 Where are these shortest paths? 491 00:25:34,560 --> 00:25:39,540 Well, I can go from A, to D to B 492 00:25:39,540 --> 00:25:41,390 and that's nine minus eight. 493 00:25:41,390 --> 00:25:46,390 So this distance should be one arriving from D 494 00:25:46,900 --> 00:25:51,670 and I should be able to go from A to D to B, to C 495 00:25:55,920 --> 00:25:59,980 and that'll give me a distance of six arriving from B. 496 00:25:59,980 --> 00:26:02,150 So you see Dijkstra's algorithm, 497 00:26:02,150 --> 00:26:04,170 when there's a negative weight 498 00:26:04,170 --> 00:26:08,453 can fail to find the shortest paths. 499 00:26:10,140 --> 00:26:11,890 Negatives weights do not work 500 00:26:11,890 --> 00:26:14,400 with Dijkstra's greedy approach, okay? 501 00:26:14,400 --> 00:26:16,923 So keep that in mind. 502 00:26:17,950 --> 00:26:20,560 What else, can we do do better? 503 00:26:20,560 --> 00:26:22,610 We've seen that the worst case complexity 504 00:26:22,610 --> 00:26:25,410 is big O of cardinality V 505 00:26:25,410 --> 00:26:29,203 plus the cardinality V times the log of the cardinality V. 506 00:26:31,880 --> 00:26:33,140 Can we do better than that? 507 00:26:33,140 --> 00:26:36,950 Well, in special cases, we can. 508 00:26:36,950 --> 00:26:41,950 So here in the graph above it has the same node set 509 00:26:43,860 --> 00:26:46,400 as the graph that we saw earlier 510 00:26:46,400 --> 00:26:50,670 but I've rearranged the edges so as to remove cycles. 511 00:26:50,670 --> 00:26:55,410 So the graph that we worked our example on had cycles in it, 512 00:26:55,410 --> 00:26:57,640 this one is a cyclic 513 00:26:57,640 --> 00:27:01,810 and you'll recall that for every directed acyclic graph, 514 00:27:01,810 --> 00:27:05,350 there's at least one top illogical sort. 515 00:27:05,350 --> 00:27:09,570 And so here we have a directed acyclic graph 516 00:27:09,570 --> 00:27:12,840 and below is just rearranging the vertices 517 00:27:12,840 --> 00:27:16,340 to show a topological sort for this graph. 518 00:27:16,340 --> 00:27:21,340 So we have A, B, C, D H L K J and F in that order. 519 00:27:21,970 --> 00:27:26,150 And so that provides us with a convenient linear order 520 00:27:26,150 --> 00:27:28,410 to our vertices. 521 00:27:28,410 --> 00:27:33,410 And we can proceed through these nodes in a linear fashion 522 00:27:34,810 --> 00:27:37,930 and we don't need to maintain them in a priority queue. 523 00:27:37,930 --> 00:27:41,740 So the overhead of working with priority queue is gone. 524 00:27:41,740 --> 00:27:44,360 And so this makes this a little faster. 525 00:27:44,360 --> 00:27:49,360 So in the case of a directed a cyclic graph, 526 00:27:49,880 --> 00:27:52,670 we can perform a little better. 527 00:27:52,670 --> 00:27:54,470 Now, why does this work? 528 00:27:54,470 --> 00:27:58,870 Well, because nothing ever goes backward, right? 529 00:27:58,870 --> 00:28:00,710 In the directed acyclic graph, 530 00:28:00,710 --> 00:28:03,283 once we produce a topological sort, 531 00:28:04,390 --> 00:28:06,640 everything if we're starting at A, 532 00:28:06,640 --> 00:28:08,480 everything to the right of A, 533 00:28:08,480 --> 00:28:10,990 we're always moving in the same direction, 534 00:28:10,990 --> 00:28:13,290 we never go backward. 535 00:28:13,290 --> 00:28:15,150 And because we never go backward, 536 00:28:15,150 --> 00:28:18,210 we never have to worry about updating distance 537 00:28:18,210 --> 00:28:20,090 to a node that we've already visited. 538 00:28:20,090 --> 00:28:22,020 So this gives us the order 539 00:28:22,020 --> 00:28:24,540 in which we're gonna visit our nodes 540 00:28:24,540 --> 00:28:27,113 and we don't have to worry about priority queue. 541 00:28:27,970 --> 00:28:31,470 So in that case, the worst case complexity 542 00:28:31,470 --> 00:28:34,460 in a directed acyclic graph using topological sort 543 00:28:34,460 --> 00:28:37,600 is the same as the complexity for topological sort. 544 00:28:37,600 --> 00:28:39,510 It's big O of the cardinality V 545 00:28:39,510 --> 00:28:41,470 plus the cardinality V. 546 00:28:41,470 --> 00:28:42,573 So that's kinda cool. 547 00:28:44,860 --> 00:28:48,870 So in summary, Dijkstra's algorithm is a greedy approach. 548 00:28:48,870 --> 00:28:53,300 We grab the best answers so far, and we never backtrack. 549 00:28:53,300 --> 00:28:55,740 It's a dynamic programming approach. 550 00:28:55,740 --> 00:28:58,940 We save partial solutions along the way 551 00:28:58,940 --> 00:29:01,070 and reconstruct complete solutions 552 00:29:01,070 --> 00:29:02,430 from the partial solutions. 553 00:29:02,430 --> 00:29:04,260 That's how we were able to say 554 00:29:05,410 --> 00:29:08,250 what the shortest path was between A and L 555 00:29:08,250 --> 00:29:09,690 in the example that we worked out 556 00:29:09,690 --> 00:29:12,020 we went to L and we worked backward 557 00:29:12,020 --> 00:29:14,300 through all those pointers until we got back to A 558 00:29:14,300 --> 00:29:16,963 reconstructing the complete solution. 559 00:29:18,370 --> 00:29:20,820 Now, what about negative weights? 560 00:29:20,820 --> 00:29:24,270 Well, negative weights are for another day. 561 00:29:24,270 --> 00:29:27,850 There's an algorithm called the Bellman-Ford algorithm. 562 00:29:27,850 --> 00:29:32,850 It runs in, I believe it's a big O 563 00:29:33,440 --> 00:29:38,440 of the cardinality V times the cardinality of E. 564 00:29:38,511 --> 00:29:41,660 And so it's slower than Dijkstra's algorithm 565 00:29:41,660 --> 00:29:43,970 but it can handle negative weights. 566 00:29:43,970 --> 00:29:46,860 And I'll either do a separate lecture 567 00:29:46,860 --> 00:29:51,860 on that, a supplemental lecture, or you'll see it in 224. 568 00:29:51,967 --> 00:29:53,853 So that's all for now, thanks.