1 00:00:06,910 --> 00:00:11,320 In this lecture, we are going to go over Dijkstra's algorithm. 2 00:00:12,610 --> 00:00:20,860 Dijkstra's algorithm is used to find the shortest path between nodes and a graph, which may represent, 3 00:00:20,860 --> 00:00:23,860 for an example, something like a road network. 4 00:00:24,460 --> 00:00:27,460 So let's build us out a simple graph here. 5 00:00:27,460 --> 00:00:43,180 So we'll have Node one, two, three and four, and we'll connect one and two with six, two and three 6 00:00:43,180 --> 00:00:52,720 with three, one and four with one or three and four with one and one and four with one. 7 00:00:53,560 --> 00:00:58,180 And we will connect one and three with four. 8 00:01:00,580 --> 00:01:03,400 So let's say we want to start out at Node one. 9 00:01:03,700 --> 00:01:15,280 So we will say our starting vertex is one and we want to find the shortest path to three. 10 00:01:17,500 --> 00:01:24,670 And well, this might be something that we obviously already kind of know how to do just by looking 11 00:01:24,670 --> 00:01:24,940 at it. 12 00:01:24,940 --> 00:01:30,880 But let's walk through it just to see what we can do for us to get to three. 13 00:01:32,080 --> 00:01:41,830 Well, if we start at one, we see that we can go and let's say we'll have paths here. 14 00:01:41,830 --> 00:01:43,690 So we start at one. 15 00:01:44,050 --> 00:01:47,800 Let's say we go one, 2 to 3. 16 00:01:47,800 --> 00:01:51,040 So one, two, three. 17 00:01:51,160 --> 00:01:53,950 Well, that would be six plus three. 18 00:01:53,950 --> 00:01:57,700 So our total weight for that would be nine. 19 00:01:58,990 --> 00:02:05,830 Let's say we went one 4 to 3, that would be two. 20 00:02:06,430 --> 00:02:09,830 And then the other one is 1 to 3. 21 00:02:09,850 --> 00:02:11,530 Well, that would be four. 22 00:02:11,980 --> 00:02:16,270 So obviously our answer to this would be two. 23 00:02:18,040 --> 00:02:26,110 Well, what if we wanted to go 1 to 2 so we could go one, two, and that would equal six. 24 00:02:27,130 --> 00:02:35,260 We could go 1 to 4 or excuse 1 to 4, and that equals one. 25 00:02:35,260 --> 00:02:40,600 And then we can go 4 to 3 and that equals one. 26 00:02:41,740 --> 00:02:44,650 And then we can go 3 to 2. 27 00:02:47,150 --> 00:02:48,370 And that equals three. 28 00:02:48,380 --> 00:02:54,110 So then we would be three plus one plus one and that equals five. 29 00:02:55,430 --> 00:03:07,790 Our other option would be 1 to 3 and that equals four and then 3 to 2 and that equals three, which 30 00:03:07,790 --> 00:03:08,690 equals seven. 31 00:03:08,690 --> 00:03:15,560 So we know that one and two are out and now one, three, two is out. 32 00:03:15,560 --> 00:03:18,650 So our shortest path for 1 to 2. 33 00:03:18,650 --> 00:03:25,640 So from 1 to 2, our shortest path would be to one for 34 00:03:29,270 --> 00:03:31,820 three two. 35 00:03:34,970 --> 00:03:38,810 So that's basically how Dijkstra's algorithm works. 36 00:03:39,470 --> 00:03:48,440 We are evaluating the weight of the edges between all the nodes, and we are going to evaluate all the 37 00:03:48,440 --> 00:03:55,520 possible paths that we can have and determine which one has the lowest weight, and that will be the 38 00:03:55,520 --> 00:03:58,430 most efficient path for us to take. 39 00:03:58,550 --> 00:04:04,040 So in the next lecture, we're going to see what it looks like to implement Dijkstra's algorithm and 40 00:04:04,040 --> 00:04:07,370 then run some test cases so that we can see it working in action. 41 00:04:07,580 --> 00:04:13,610 If you have any questions about Dijkstra's algorithm and how it works, please feel free to ask me in 42 00:04:13,610 --> 00:04:14,840 the Q&A section.