All right, we have the plausibility.
Now we will be developing the full service pathfinding algorithm.
That is disaster.
For this, we move inside the Fort Benning Art Park and create the class.
So we start by writing class destruct and then we define its first function.
That would be the initialize and function inside.
It will be defined the instance variable for this class and the very first instance variable would be
a state variable that basically keeps track of whether we have already used data to find the shortest
path or not.
So this would be the shortest path found and this would be initialized to false because this is the
initial action states.
Then we create the actual container that will store the shortest path once it has been found.
And this would be initialize to an empty list.
The third instance variable would be the Mini.
And the Milky Way will be used to create the priority queue.
That is a necessity for the disaster algorithm and this would be initialized to the heap class object
that we created earlier.
And finally, we'll be creating two dictionaries that basically stores the relationship between Vertex
and the responding corresponding indices.
And why are we creating these two dictionaries will be apparently drawn at this moment.
They are just named as indices to what it is.
And where does this indices to basically contain, to convert the vertex to index and index to the vertex.
And then we proceed to perform or create the next function for this class.
That would be the final results are the five vessels is name as such and not fine, but because this
particular algorithm of destroyer not only find the shortest path to the goal, but also all the sub
parts of the short distance between the respective nodes.
This is why it is named as fine vessels because it finds the best results.
So we proceed inside it and the very first thing that we need to do is create the index for our start
vertex and why do we need to do that?
The reason is that the information that can be stored inside the mean heap cannot be the vertex itself
because he only takes in integers as an argument.
So we need to convert the vertex which is in tuple to some other integer format and that is the best
thing that can be stored is basically the index of that vertex.
So we stored that index in just replacing its vertex.
So this is why we required index for each vertex for all vertex that will be using.
So we require the index for our start vertex.
And that would be named as starter index.
And that would be created as using list comprehension.
Now the various comprehension works we enter define which type or what type of list do we want to create.
So we want to create the list for the indices.
But where do we get the industries for?
So we get the indices form by looping over indices for indices.
And by using an order that loops over an well, that would be the graph items.
So we tried graph items and once we have loop over the graph items, we now call the condition that
which indices do we want to store inside the index list?
And that would be right on right here.
That if.
The key that is a vortex is equally equal to the start vortex.
So if such a condition arise that when we are looping over the keys present inside the graph and that
key is equal to our start vertex then stored index for that vertex and that will be the start vertex.
And then we only keep the first index if we have multiple matches.
So this gives us the stock index.
Once we have this information, we create two new lists and that would be a distance list and the parent
list.
Now, this list is basically just a list to store the distances for each corresponding vertex.
And apparently, as is used to store the closest vertex for all vertices.
And next we create or update the min heap size that we'll be creating later on.
So the heap size is basically storing all the words that are present inside the graph.
So all the graph keys or the number of graph keys is basically going to be the size of the heap once
it has been created.
So we update this variable so that we know what is the size of the main heap or the priority group.
Then we proceed to iterate over our graph keys.
And this would this would be done to initialize our mean heap that we were done before in enumerate
enumerate.
And we would be iterating over our graph keys.
We're writing, graphed our keys, enumerate.
And this provides us enumerate, provides us the index and the vertex present inside those keys, inside
those graph.
So we not only have the iterable, but also the value of that iterable.
That is the vertex.
So we are going to use this information in creating our mean heap and our distance list.
So we start by updating our distance list.
And that will be done very simply by writing or appending.
Appending infinity to our distance list.
And this would be named as one into ten, five minus ten by seven, and we initialize our distances
for each vertex to infinity.
And this is the first step for attempting the diaspora algorithm.
Then we proceed to creating our main array from our notes that are present inside our graph.
So that will be done by accessing the main heap object, by writing surfboard 20 and accessing it's
only and now because it was a list, access is a function of append for that list and here we open each
node and we create each node and then append it to the array.
That is a list for our mean.
So that is done by accessing the functional main heap that is new in heap node.
This creates a new meaning of Node partaking in two arguments.
The fourth is the vertex and second is a distance of that vertex.
But the problem is, as mentioned earlier, we cannot store the vertex because it is in tuple format,
but the mini heap only takes in the integer format.
So we need to store something as that replaces our vertex and that that thing that will be replacing
that vertex with will be the index of that vertex.
So we instead of the V, we right here, the index and for the distance you provide in the distance
of that vertex and that will be distance for that index.
And once you have stored this information, we proceed further because our mean heap, once this loops
completes, has been collated or created completely, then to create the next instance variable for
our main heap or update our mean heap instance variable that is collection of where does this basically
store the position of vertex for our heap and that will be initialized appended.
With the index of that vertex.
So instead of the verses we are storing here, sorting here, the index of that vertex.
And this is basically the position of that vertex.
Now, once you're done with this, we proceed to open our parent variable with negative one.
And that would be done.
Because if if we do not find any close vertex for any of the for any vertex, then we would know that
we were unable to find the close vertex for that particular note.
And that would be known by having a value of negative one.
Otherwise it would be updated.
Any other value.
And finally, what we will do is we will update our dictionaries that basically store the relationship
between vertices and the indices.
And that will be done by writing support workers to indices and providing in the Vertex ASCII.
Because we are basically converting or creating a dictionary that converts the vertex or vertex to indices.
So vertex would be the key and index would be the value.
So if we provide vertex to this dictionary, it gives us the index and the opposite books in the indices
towards additionally where we provide in the index.
And this gives us the vertex as the body value.
So if we want to stretch either of the vertex or the index, we can do by simply accessing these dictionaries
and providing in the respective key.
Now that we have initialize the mini pre and also set the distance of each corresponding vertex to infinity,
we can now proceed to the second step for our DICE algorithm and that is to simply decrease the key
for our start vertex from infinity down to zero.
So the way this works is that we access the distances and passing the index of the start vertex to the
start index and decrease this value down to zero.
And because we have updated the value inside the distances, we need to do the same inside the mean
heap.
And that is done by accessing its function of decrease key.
Now this function fixing to input argument the force is the vortex of which you want to decrease the
key off.
And second is the newly formed shortest distance.
So for the vertex we provide this corresponding index that is the start index.
And for the distance we provided the newly falling short assistance.
That is a distance of the start index.
And what this function of decrease key will do will basically decrease this particular start index value
inside the mean heap.
And this would basically take it right to the top of our main heap or the priority queue, because it
would have the minimum value and the highest priority next.
We simply create a loop that is a value.
And this would run for as long as the main heap or the priority queue has an inside of it.
So that can be accessed by accessing the min heap and checking its size variable and that is not equal
to zero.
So if it is if it has still a node inside of it, then we can continue this loop.
Otherwise we stop the loop.
So the very first thing that we do inside this group is extract the node with the minimum value, and
that can be done by accessing the main function of extract min.
And this node would be our start vertex because it has the minimum value, because every other node
has the value or distance of infinity.
And let's call this minimum value node as currently because it is at the top.
So once we have this current of and this would be of the type integer and this is the indices and distance
of those indices.
So we simply extract the index of that particular note and that can be extracted as you index.
And we access this from the current Top Zero Index.
Now, because we have the index of our current node, we also require the vertex of this current node.
And that can be done by accessing that dictionary that we earlier that was the indices to vertices.
So we have the index it providing the index of U index.
On the correct note and we and we will retrieve the current note and rename it.
Now, once we have the right note and its corresponding index, we can now access its neighbor nodes
per our current node and that can be done by accessing by writing for neighbor node.
Let's call them B for B in graph, providing the current node you.
So now the V is in the form of tuple.
That is the neighbor node for our graph.
So we start all by checking if the neighbor node is not equal to case because we don't want to do anything
with the case.
No, that is done by writing if condition if we are not equal to case because we don't want to do or
take care of case notes.
So if we have the b b node now, it will be the vertex and we require its corresponding index.
So that can be accessed for writing the index from the dictionary that basically converts the vertices
to indices.
So I provide in the vertex that is the neighbor node we and the neighbor node we.
Index.
Once we have this information, we can now perform a few checks to check whether we have found a shortest
distance from our cart, nor to the neighbor.
Not the way the sick work is that we first check whether the neighbor node is part of the main heap
or not.
Because if it is not part of the mean, that means it's already visited.
So we don't visit that note and then we check if the distance of the car door is not equal to infinity.
Because if it is equal to infinity, then we are not proceeding correctly.
And then finally, we check if we have found the shortest shorter distance from the previously known
shorter distance for our neighbor node.
And that is done by finding the traversal cost of our current or neighbor node and then adding that
to the distance for our control.
And if it is less than the distance of known distance for our neighbor node, then we update the distance
for our neighbor, not because we have found a new shorter distance and that is done by simply starting
working distance.
We index and we write here.
The graph or traversal cost from grant node to neighbor node accessing this cost and adding the adding
the distance of the current note.
So this is the newly found chart of distance.
And because we have updated the distance for our neighbor node, we need to do the same inside the mean.
And that is done by writing when he not decreasing.
And this takes in two input argument one.
First is the vertex of which we want to decrease the key kilo.
And because you are decreasing the key of our neighbor node, that is a V indexed.
So we provide in the V index and then we provide in the updated V in this distance.
And this is basically decrease the key of this neighbor note.
Then we simply update the newly found closest vertex for our neighbor node.
And that is done by accessing the parent list and it providing the index of our neighbor node and provide
the information of the newly found parent for our neighbor node.
That is the U index because that has a distance shorter than the previously known distance for our neighbor
node.
Now, once you're done with this, we can now simply add a condition or end condition for our distance
algorithm, because otherwise this function will loop until the priority queue is empty.
So if you want to stop it earlier, when we have reached our end node and that would be when we are
visiting and when our current node is a neighbor.
Note Because when we have visited the current node and or when we have bought the current.
That means that we have found the shortest distance to the current note.
So we don't need to proceed further.
So we simply add that end condition greater over here.
We simply say that if our current node is the end node, then we have found the shortest distance to
the to the gold node.
So to access the shortest out to the goal note to create a new function, that access is on the finished
list.
And that would be known as.
Certain shortcuts don't.
Now this particular function takes in three or four input arguments.
The first is the parent list, which has the close vertex for all corresponding vertices, and then
the start node and then the end of the go note and then the root, which will basically store the shortest
down to the goal.
So now we need to call this particular function.
Right over here, which is basically surfboard return shorted up the sticks in the parent list, then
the start node and at the end node and here for the routing, providing the shortest path list.
And this would become populated with the shortest path to the goal.
So we need to create this, this variable of shortest path container for the shortest path, and we
initialize this to an empty list.
And when this function runs it, find the shortest path to the goal from the parent or the closed vertex
list.
And then stores this inside the shortest spot list.
Sorry.
I missed my word.
Once I have this information.
We aim to store the shortest part inside our instance variable of shorter spot.
And that can be done very simply by simply reversing our a spot that is in the reverse.
Reverse this list.
Store this.
Inside this shortest instance variable.
And then set our boolean variable or shortest path to true because the Dijkstra algorithm was successful
in finding the shortest path to go.
So this dataset algorithm definition is now completed and all that is there for us to do.
It is simply integrated to our main project and see what finds the shortest path to the goal.
Right.
In the previous coding session, we developed the dice algorithm and now all that is left for us to
do is to simply integrated to our project.
For this, you move inside the board part, then a clause.
We are in the new instance variable or dice this guess assigned object of the dice class.
Then we move to the find path and display a function that actually finds the path to the goal.
And we provide in the new method that we have justifying that is a dice for algorithm inside it.
We simply check if the shortest path is not already found or not.
So if it hasn't been found as of yet, then we find the shortest path to the goal by calling the function
of dice to class.
That is fine but starts this takes in three input arguments.
The first is the graph that is the output of the mapping algorithm and then the start and end vertex,
the goal of which you want to find the shortest path up.
Then this obvious, the shortest part is just variable.
And then we assign this value for the path to display variable.
Then we simply display that shortest path back onto the maze from which it was expected.
And this is displayed to the user in the form of a colourful thought.
Then we can head over to the Miss Salvador part where we have called the function of find and display
to find the shortest out the goal using specified method previously where you were using DFS.
And now we modify this to use the currently made dice to algorithm.
So we right here.
Destruct as the method that should be used for finding the path to the goal.
Now, once we sign this, we save this and head over to the terminal building project.
I've already started simulation.
So we run the maze solver.
Once this runs, you will see the output of the locals and state.
Then you press spacebar again.
This outputs the output of mapping state, passing the spacebar again.
Woops.
We have landed on an error and the error stays at the rotor again.
This line was unable to work because of a key error and we're passing in tuples so this tuple cannot
be accessed from cannot be accessed for this index to vertices.
Now this problem is occurring because we want to convert an index to vertex, but we are providing in
vertex.
So why is this happening?
So we have provided and that is not index but rather the vertex.
So we need to provide here that the proper index of that particular vertex.
So what we do right here is we head on over to the board part, then the part where we have defined
the distal clause.
I don't want to head over to the find results.
Right in the bottom where we have called the function of written short shortstop.
We have passing in the parent class, but the parent class only gives the closest vertex index for each
corresponding vertex index.
So we do not provide in the start vertex, but rather you should provide here the start index.
And for the end we also providing an index so we already have the START index.
So we like to start indexed, but we don't have the end index.
So we can compute that by accessing our.
Visionary that converts the vertex to indices.
So it falls in the vortex of RN and retrieved an index.
And you provide it to the written shortlist round and hopefully the error will go away.
And I will build this project again.
And this time we run the simulation.
After the localizing stage, we have the map and state pressing experience, but again, we retrieve
the output of the dice algorithm.
And as you can see, this current line showed the path from the maze entry to the maze exit, which
is the actual shortest path found using the Die Star algorithm.
So this seems to be correct.
So now we can proceed to finding the shortest path using the estar algorithm and see if it does a better
job in finding the shortest spot till then.
Thank you.
And.
But.