1
00:00:01,060 --> 00:00:08,500
Finding a path or possible path using DFS was good and all, but what if you wanted to find the shortest

2
00:00:08,530 --> 00:00:09,370
out of the goal?

3
00:00:09,790 --> 00:00:11,740
Can this be done using DFS?

4
00:00:12,280 --> 00:00:14,050
Well, in a way it can.

5
00:00:14,590 --> 00:00:17,080
It's not recommended, but it can be done.

6
00:00:17,800 --> 00:00:19,120
Let me show you how.

7
00:00:19,720 --> 00:00:25,900
If you remember the graph that we created from the Ms. in bot mapping, the structure of the graph was

8
00:00:25,900 --> 00:00:27,010
something like this.

9
00:00:28,090 --> 00:00:32,290
It has several keys representing the interest points of our minutes.

10
00:00:33,070 --> 00:00:35,620
Each key had two types of values.

11
00:00:35,950 --> 00:00:40,420
One is the case representing the case of the interest point, which we ignored.

12
00:00:40,930 --> 00:00:43,930
Second are the neighboring nodes to each respective key.

13
00:00:44,590 --> 00:00:48,140
We use these to find all possible paths to the goal.

14
00:00:48,640 --> 00:00:53,590
But if we wanted to find the shortest path to the goal, we required one additional information.

15
00:00:53,980 --> 00:00:58,420
That is the cost of traversing to each member node from its respective key.

16
00:00:59,170 --> 00:01:02,440
This information can be accessed from the neighboring nodes values.

17
00:01:02,830 --> 00:01:06,250
These are the keys and the cost of each neighboring note.

18
00:01:08,160 --> 00:01:14,130
So here we are at the boat port panicked by we are just like we defined the good false function to find

19
00:01:14,160 --> 00:01:15,780
all possible roles to the goal.

20
00:01:16,110 --> 00:01:22,740
We have defined the get pass cost function to define all possible paths to the goal and also the destructive

21
00:01:22,740 --> 00:01:23,100
cost.

22
00:01:23,490 --> 00:01:28,440
The reason we are trying to find the respective goals for all possible paths is because we wanted to

23
00:01:28,440 --> 00:01:33,870
find the shortest route to the goal and the shortest out of the goal will have the least amount cost.

24
00:01:34,440 --> 00:01:40,110
Now to explain this get pass cost function that I would define are only defining or identifying the

25
00:01:40,110 --> 00:01:45,990
differences from this function to the original, because everything else is exactly the same in the

26
00:01:45,990 --> 00:01:46,620
arguments.

27
00:01:46,620 --> 00:01:47,850
We have two new arguments.

28
00:01:47,850 --> 00:01:51,000
That is the total cost of reaching that rule.

29
00:01:51,150 --> 00:01:56,400
And if there was low cost or the cost of traversing from the start node to the neighbor node and both

30
00:01:56,400 --> 00:01:57,930
of these initialize to zero.

31
00:01:58,500 --> 00:02:04,080
Then after we have concatenated the wasted node to the part we will be earning, there will still cost

32
00:02:04,500 --> 00:02:05,430
to the total cost.

33
00:02:06,060 --> 00:02:11,490
Then after we initialize the boss variables to store all possible paths, we will initialize the cost

34
00:02:11,490 --> 00:02:15,600
variable to store the respective cost for all found path to the goal.

35
00:02:16,200 --> 00:02:22,380
Then when we have recursively cost the get passed cost function, we will be adding the two new arguments

36
00:02:22,380 --> 00:02:24,240
for the total cost and the table.

37
00:02:24,240 --> 00:02:28,920
So cost of start node to the neighbor node by accessing its value of cost.

38
00:02:29,550 --> 00:02:35,550
So this function retrieved as the new path and new cost of reaching the goal for all possible path of

39
00:02:35,550 --> 00:02:39,120
reaching the goal and the respective cost by returning it to the user.

40
00:02:39,660 --> 00:02:44,310
So this is the modification that we did and retrieve the get passed cost function.

41
00:02:44,700 --> 00:02:49,890
And now we head on over to the path planner where we have the find path and display function.

42
00:02:50,160 --> 00:02:56,430
And in this function we will be updating the method from DFS could be a first shortlist when the user

43
00:02:56,430 --> 00:03:02,760
mentioned that he wants to find the shortest path to the goal by writing DFS shortest, it will use

44
00:03:02,760 --> 00:03:07,980
the DFS algorithm to find the shortest out of the group it calls the get pass cost function.

45
00:03:08,210 --> 00:03:11,310
Retrieve the path and the respective cost to the goal.

46
00:03:12,120 --> 00:03:18,090
Using the cost, we find the cost or the path with the minimum deposit cost and using the index you

47
00:03:18,090 --> 00:03:24,390
find the shortest spot because it has the minimum traversal cost and we use that path to display the

48
00:03:24,420 --> 00:03:27,990
spirit of the user using that drop path on Miss.

49
00:03:28,260 --> 00:03:33,720
And now we head on over to the Ms. Salvador part where we have called this function of find path and

50
00:03:33,720 --> 00:03:34,140
the split.

51
00:03:34,680 --> 00:03:40,440
At this moment it is using the method that a default method of DFS and finding all possible path to

52
00:03:40,440 --> 00:03:43,860
the goal for if we want to find the shortest out of the gold.

53
00:03:45,520 --> 00:03:46,870
You're the boss in the method.

54
00:03:48,200 --> 00:03:50,240
S DFS shortlist.

55
00:03:51,180 --> 00:03:57,060
So this will simply call this all possible path to the goal and the respective calls to find the shortest

56
00:03:57,060 --> 00:03:57,930
path to the goal.

57
00:03:58,650 --> 00:04:02,820
Now, if I don't know what we are doing, I have already started the simulation.

58
00:04:04,740 --> 00:04:05,760
Build this project.

59
00:04:08,880 --> 00:04:10,620
And then randomly solving.

60
00:04:11,580 --> 00:04:16,890
Now, once the localization module has been completed, you will see this occupancy rate pressing the

61
00:04:16,890 --> 00:04:17,550
spacebar.

62
00:04:17,790 --> 00:04:20,580
You will receive the output of the mapping module.

63
00:04:20,850 --> 00:04:21,750
Pressing spacebar.

64
00:04:21,750 --> 00:04:27,480
Again, you have the output of the port planner that is using the method to find the shortest path to

65
00:04:27,480 --> 00:04:28,920
the goal using DFS.

66
00:04:29,250 --> 00:04:34,800
And as you can see, this colored line indicates that we have found the shortest path to the goal.

67
00:04:35,160 --> 00:04:40,710
And if you observe this port, you can indeed see that this is indeed the shortest road from the maze

68
00:04:40,710 --> 00:04:42,390
entry to the Maze exit.

69
00:04:42,780 --> 00:04:49,800
So the DFS can indeed be used to find the shortest path to the goal, but it was not recommended to

70
00:04:49,800 --> 00:04:55,770
you to find the shortest path to the goal using DFS because the method that it employs to find the shortest

71
00:04:55,770 --> 00:04:57,690
path is just too cumbersome.

72
00:04:57,960 --> 00:05:03,530
It finds all possible paths to the goal and tries to find the path with a minimum traversal cost.

73
00:05:04,080 --> 00:05:11,190
So basically it is running for finding all possible paths and not running intelligently to find the

74
00:05:11,190 --> 00:05:11,880
shortest path.

75
00:05:12,390 --> 00:05:18,630
So there are other algorithms that are dedicated this task of find the shortest out of the goal, and

76
00:05:18,840 --> 00:05:21,330
these are the algorithm that we will be starting next.

77
00:05:21,660 --> 00:05:25,740
These will be nice to and is to build in.

78
00:05:26,100 --> 00:05:26,670
Thank you.

79
00:05:26,940 --> 00:05:27,180
And.

80
00:05:27,180 --> 00:05:27,510
But.