Finding a path or possible path using DFS was good and all, but what if you wanted to find the shortest
out of the goal?
Can this be done using DFS?
Well, in a way it can.
It's not recommended, but it can be done.
Let me show you how.
If you remember the graph that we created from the Ms. in bot mapping, the structure of the graph was
something like this.
It has several keys representing the interest points of our minutes.
Each key had two types of values.
One is the case representing the case of the interest point, which we ignored.
Second are the neighboring nodes to each respective key.
We use these to find all possible paths to the goal.
But if we wanted to find the shortest path to the goal, we required one additional information.
That is the cost of traversing to each member node from its respective key.
This information can be accessed from the neighboring nodes values.
These are the keys and the cost of each neighboring note.
So here we are at the boat port panicked by we are just like we defined the good false function to find
all possible roles to the goal.
We have defined the get pass cost function to define all possible paths to the goal and also the destructive
cost.
The reason we are trying to find the respective goals for all possible paths is because we wanted to
find the shortest route to the goal and the shortest out of the goal will have the least amount cost.
Now to explain this get pass cost function that I would define are only defining or identifying the
differences from this function to the original, because everything else is exactly the same in the
arguments.
We have two new arguments.
That is the total cost of reaching that rule.
And if there was low cost or the cost of traversing from the start node to the neighbor node and both
of these initialize to zero.
Then after we have concatenated the wasted node to the part we will be earning, there will still cost
to the total cost.
Then after we initialize the boss variables to store all possible paths, we will initialize the cost
variable to store the respective cost for all found path to the goal.
Then when we have recursively cost the get passed cost function, we will be adding the two new arguments
for the total cost and the table.
So cost of start node to the neighbor node by accessing its value of cost.
So this function retrieved as the new path and new cost of reaching the goal for all possible path of
reaching the goal and the respective cost by returning it to the user.
So this is the modification that we did and retrieve the get passed cost function.
And now we head on over to the path planner where we have the find path and display function.
And in this function we will be updating the method from DFS could be a first shortlist when the user
mentioned that he wants to find the shortest path to the goal by writing DFS shortest, it will use
the DFS algorithm to find the shortest out of the group it calls the get pass cost function.
Retrieve the path and the respective cost to the goal.
Using the cost, we find the cost or the path with the minimum deposit cost and using the index you
find the shortest spot because it has the minimum traversal cost and we use that path to display the
spirit of the user using that drop path on Miss.
And now we head on over to the Ms. Salvador part where we have called this function of find path and
the split.
At this moment it is using the method that a default method of DFS and finding all possible path to
the goal for if we want to find the shortest out of the gold.
You're the boss in the method.
S DFS shortlist.
So this will simply call this all possible path to the goal and the respective calls to find the shortest
path to the goal.
Now, if I don't know what we are doing, I have already started the simulation.
Build this project.
And then randomly solving.
Now, once the localization module has been completed, you will see this occupancy rate pressing the
spacebar.
You will receive the output of the mapping module.
Pressing spacebar.
Again, you have the output of the port planner that is using the method to find the shortest path to
the goal using DFS.
And as you can see, this colored line indicates that we have found the shortest path to the goal.
And if you observe this port, you can indeed see that this is indeed the shortest road from the maze
entry to the Maze exit.
So the DFS can indeed be used to find the shortest path to the goal, but it was not recommended to
you to find the shortest path to the goal using DFS because the method that it employs to find the shortest
path is just too cumbersome.
It finds all possible paths to the goal and tries to find the path with a minimum traversal cost.
So basically it is running for finding all possible paths and not running intelligently to find the
shortest path.
So there are other algorithms that are dedicated this task of find the shortest out of the goal, and
these are the algorithm that we will be starting next.
These will be nice to and is to build in.
Thank you.
And.
But.