So breakfast was adequate.
We're only concerned with finding a path from the start to the goal alone and not concern whether it
was the best possible path or not.
But if we did want to find the most optimal path, we would opt for algorithms other than DFS or DFS
algorithms that there was some cost into account while making a decision on which note to visit first.
One such algorithm is distro.
This is a greedy search algorithm.
And the reason it's greedy, the goal is always selects the best option in choosing the next spot to
visit.
This selection of best option is based on the list reversal caused from the start node to the current
node, and if it does manage to find a shorter part, it updates the previously known short.
I thought this property not only helps it to find the shortest path from the start node to the goal
node, but also all the supports are of the shortest line between the respective nodes.
This algorithm stops when either all the nodes have been visited or the shortest path between the start
node and the goal node has been found.
Now let's look at an example to better understand the inner workings of Nice to.
So we have a simple grow will start notice if an end node is C.
And we draw a table on the right, which has three columns.
There is what is the least cost to visit and the previous or the closest vertex.
Initially we said the least cost to visit to 8 to 0 because we are already at eight and we don't need
to move any further.
And for all the other nodes, we set them to infinity because we don't know what's the cost of traversing
those nodes as of yet.
So we move on to step one.
For the step one, we now visit just the nodes of eight, which are B, C and D, and they have all
have a traversing cost that is less than infinity.
So we update least cost to visit for these respective nodes.
So for B, it becomes four, for C it becomes six, and for D it becomes two.
And because all of these nodes have the shortest path through it and it's close, vertex is there.
So we update that column by writing it.
For the next step, we visit the nose that has the least sort of cost.
So at the moment, the only unvisited node that has the least cost is D and has a total cost of two.
So we visit D next.
So.
Visiting the now opens a new pathway to see that is from A to B and D to C.
But this path has a traversal cost of two plus seven, nine and nine is greater than six.
So we haven't found a shortest path than the previously known short of thought.
So we don't do anything right here.
We move on to the next unvisited note that has the least cost.
So the next unvisited note that has the least cost is B, which has lowest cost of four.
A visiting bee.
Next you will see that another part opens up to see that has a traversing cost of four +15.
This servicing cost of five is less than the previously known shortest distance to see which was from
a to see.
So we update the shortest distance that goes to see from 6 to 5 an update ending.
This means that the close vertex is not A, but rather now b.
And now finally we visit the unvisited node that is left that is sea.
So once we visit unvisited node, all those have been visited.
So the algorithm starts right here.
So the shortest path from our start node to the goal node is from a.
To be and B to see this has a cost or a difference in cost of five.
And we have found the shortest path from the start to the goal node.
So this is how it dies to find the shortest path towards this goal node.
Now let us look at a few notable characteristics of this step.
Our data is both complete and optimal.
And the reason it is that because it not only finds a path if it exists, but also that path is guaranteed
to be as short as length.
Then it also requires the implementation of a priority group.
This is to always visit the node with the least members and cost.
Now let us look at a few important applications of.
Starting with the first there is a GPUs which we use to find out from our location.
The location we want to go next is the air in games where the paths and supports are found for different
goals in games.
Now all this is very handy, but Die Start does come with a few limitations.
For example, it can only work for the positively weighted golf or negatively weighted drop.
It gives incorrect short spot estimations.
And number two.
This drug is inefficient.
And the reason it is interesting because it only takes the images neighbors into account while traversing
different nodes.
This shortsightedness often leads to visiting more north than this city and finding the shortest path
to go.