1 00:00:00,970 --> 00:00:02,590 So breakfast was adequate. 2 00:00:02,940 --> 00:00:08,050 We're only concerned with finding a path from the start to the goal alone and not concern whether it 3 00:00:08,050 --> 00:00:10,180 was the best possible path or not. 4 00:00:10,870 --> 00:00:17,260 But if we did want to find the most optimal path, we would opt for algorithms other than DFS or DFS 5 00:00:17,740 --> 00:00:23,710 algorithms that there was some cost into account while making a decision on which note to visit first. 6 00:00:24,430 --> 00:00:26,800 One such algorithm is distro. 7 00:00:29,110 --> 00:00:31,510 This is a greedy search algorithm. 8 00:00:31,690 --> 00:00:37,330 And the reason it's greedy, the goal is always selects the best option in choosing the next spot to 9 00:00:37,330 --> 00:00:37,720 visit. 10 00:00:38,140 --> 00:00:43,930 This selection of best option is based on the list reversal caused from the start node to the current 11 00:00:43,930 --> 00:00:49,420 node, and if it does manage to find a shorter part, it updates the previously known short. 12 00:00:49,420 --> 00:00:55,090 I thought this property not only helps it to find the shortest path from the start node to the goal 13 00:00:55,090 --> 00:01:00,880 node, but also all the supports are of the shortest line between the respective nodes. 14 00:01:01,450 --> 00:01:07,930 This algorithm stops when either all the nodes have been visited or the shortest path between the start 15 00:01:07,930 --> 00:01:09,940 node and the goal node has been found. 16 00:01:10,690 --> 00:01:15,010 Now let's look at an example to better understand the inner workings of Nice to. 17 00:01:16,130 --> 00:01:21,290 So we have a simple grow will start notice if an end node is C. 18 00:01:22,530 --> 00:01:25,530 And we draw a table on the right, which has three columns. 19 00:01:25,890 --> 00:01:31,020 There is what is the least cost to visit and the previous or the closest vertex. 20 00:01:31,740 --> 00:01:38,310 Initially we said the least cost to visit to 8 to 0 because we are already at eight and we don't need 21 00:01:38,310 --> 00:01:39,270 to move any further. 22 00:01:39,840 --> 00:01:46,320 And for all the other nodes, we set them to infinity because we don't know what's the cost of traversing 23 00:01:46,320 --> 00:01:47,820 those nodes as of yet. 24 00:01:48,750 --> 00:01:50,130 So we move on to step one. 25 00:01:51,060 --> 00:01:59,460 For the step one, we now visit just the nodes of eight, which are B, C and D, and they have all 26 00:01:59,460 --> 00:02:02,220 have a traversing cost that is less than infinity. 27 00:02:02,370 --> 00:02:05,880 So we update least cost to visit for these respective nodes. 28 00:02:06,270 --> 00:02:12,840 So for B, it becomes four, for C it becomes six, and for D it becomes two. 29 00:02:13,080 --> 00:02:18,600 And because all of these nodes have the shortest path through it and it's close, vertex is there. 30 00:02:18,690 --> 00:02:22,070 So we update that column by writing it. 31 00:02:24,370 --> 00:02:28,420 For the next step, we visit the nose that has the least sort of cost. 32 00:02:28,750 --> 00:02:35,650 So at the moment, the only unvisited node that has the least cost is D and has a total cost of two. 33 00:02:36,160 --> 00:02:37,330 So we visit D next. 34 00:02:40,430 --> 00:02:40,790 So. 35 00:02:42,020 --> 00:02:47,900 Visiting the now opens a new pathway to see that is from A to B and D to C. 36 00:02:48,230 --> 00:02:53,540 But this path has a traversal cost of two plus seven, nine and nine is greater than six. 37 00:02:53,810 --> 00:02:57,590 So we haven't found a shortest path than the previously known short of thought. 38 00:02:57,890 --> 00:02:59,660 So we don't do anything right here. 39 00:03:00,170 --> 00:03:03,680 We move on to the next unvisited note that has the least cost. 40 00:03:04,100 --> 00:03:09,770 So the next unvisited note that has the least cost is B, which has lowest cost of four. 41 00:03:11,300 --> 00:03:12,140 A visiting bee. 42 00:03:12,140 --> 00:03:20,690 Next you will see that another part opens up to see that has a traversing cost of four +15. 43 00:03:21,440 --> 00:03:27,470 This servicing cost of five is less than the previously known shortest distance to see which was from 44 00:03:27,470 --> 00:03:28,070 a to see. 45 00:03:28,280 --> 00:03:35,490 So we update the shortest distance that goes to see from 6 to 5 an update ending. 46 00:03:35,510 --> 00:03:40,790 This means that the close vertex is not A, but rather now b. 47 00:03:42,180 --> 00:03:46,440 And now finally we visit the unvisited node that is left that is sea. 48 00:03:46,830 --> 00:03:50,400 So once we visit unvisited node, all those have been visited. 49 00:03:50,580 --> 00:03:52,200 So the algorithm starts right here. 50 00:03:52,680 --> 00:03:56,700 So the shortest path from our start node to the goal node is from a. 51 00:03:57,740 --> 00:04:03,560 To be and B to see this has a cost or a difference in cost of five. 52 00:04:03,890 --> 00:04:06,970 And we have found the shortest path from the start to the goal node. 53 00:04:07,430 --> 00:04:11,210 So this is how it dies to find the shortest path towards this goal node. 54 00:04:12,810 --> 00:04:15,990 Now let us look at a few notable characteristics of this step. 55 00:04:18,840 --> 00:04:21,870 Our data is both complete and optimal. 56 00:04:22,470 --> 00:04:28,950 And the reason it is that because it not only finds a path if it exists, but also that path is guaranteed 57 00:04:29,100 --> 00:04:30,210 to be as short as length. 58 00:04:31,030 --> 00:04:34,670 Then it also requires the implementation of a priority group. 59 00:04:34,980 --> 00:04:38,100 This is to always visit the node with the least members and cost. 60 00:04:39,120 --> 00:04:42,180 Now let us look at a few important applications of. 61 00:04:43,170 --> 00:04:48,210 Starting with the first there is a GPUs which we use to find out from our location. 62 00:04:48,330 --> 00:04:56,370 The location we want to go next is the air in games where the paths and supports are found for different 63 00:04:56,370 --> 00:04:57,270 goals in games. 64 00:04:58,150 --> 00:05:02,100 Now all this is very handy, but Die Start does come with a few limitations. 65 00:05:03,000 --> 00:05:08,820 For example, it can only work for the positively weighted golf or negatively weighted drop. 66 00:05:09,240 --> 00:05:12,210 It gives incorrect short spot estimations. 67 00:05:13,050 --> 00:05:13,830 And number two. 68 00:05:14,900 --> 00:05:16,680 This drug is inefficient. 69 00:05:17,040 --> 00:05:22,830 And the reason it is interesting because it only takes the images neighbors into account while traversing 70 00:05:22,830 --> 00:05:23,580 different nodes. 71 00:05:24,120 --> 00:05:29,640 This shortsightedness often leads to visiting more north than this city and finding the shortest path 72 00:05:29,640 --> 00:05:30,180 to go.