In this lecture, we're going to begin going over a possible implementation for Dijkstra's algorithm.
Now, there are many ways that Dijkstra's algorithm can be implemented.
So I encourage you after this lecture to potentially think of other ways and methods that we would be
able to implement in this algorithm.
So before going over the implementation, we need to do a bit of setup.
The first thing that I want you to do is just go ahead and comment out everything that we did from depth
for search and breadth for search.
That way we don't have any conflicting types possible.
And then once you do that, we need to do a bit of setup before we can begin implementing in the Dijkstra's
algorithm.
So the first thing that we need to do is bring some stuff into scope.
So we're going to bring in ordering and then we're also going to bring in the binary heap collection.
Next, we want to derive a few things for the structure that we're going to create.
We're going to derive copy, clone and partial equality.
And now we can create our struct and we'll call it state, and it's going to have a field of cost of
type use, size and position of type you size as well.
So now we want to implement Ord for state, so we'll say implement Ord for state.
So we're implementing ordering for state and we will say F in compare and self and then other.
With a reference to self as well, where we return ordering and what we'll do is we will say other costs
dot compare and self cost.
So you can see where this is going, where we're comparing the weight of the edge and then if there
happened to be equal, then we will just compare their positioning.
So we will say self, dot position, dot compare and other dot position.
All right.
So we are comparing the cost, aka the weights.
And then if the.
Costs are the same than we want to compare their positions.
All right.
What do we have here?
It looks like we need to implement partial equality as well.
So we will say in full or partial aud excuse me, partial aud four state and we will say if in partial
compare, and it sets all of that up for us and we will say self dot compare other.
So that was a really easy one for us to set up and that one just need to be implemented as well.
So now we can set up the edge struct, so we will say struct edge where we will have node you size and
cost you size.
And that's all we have to do in terms of setting up for what we're looking to do.
So now we can begin implementing in Dijkstra's algorithm.
So we're going to start obviously at a starting vertex and then we're going to keep track of the distance
to each node.
So what we can do is say shortest path and we will pass in our graph and we will.
And our graph is going to be a vector that a reference to a vector that contains a vector that contains
the edge.
We will have start, which is you size, and then we will have goal, which is also use size and we
will return an option of type size.
So what we're going to return is the overall cost for us to get from our start to our goal.
And we will return none that way.
We don't have any red squiggles anywhere.
And so the first thing we want to do is keep track of the distances.
So we will say let meet distance is equal to vector of a type that we don't care about.
And we will say from zero to graph dot length map these values that we do not care about.
And we will say you size max dot.
Correct.
So what we are doing here is saying, hey, for all of our distance, go ahead and make them the max
size.
That way, when we look at the actual distance, we get a good comparison of.
What we want, right?
So if it's you size max, then when we compare it to the distance inside of our vector here, we'll
be able to update that accordingly with the edges cost.
So now we want to create our visited and we will say binary heap new.
So we know that our starting distance is always going to be zero because that is where we starting at
and we will push this into visit it since that is where we are currently at.
So we will say state our cost is zero and our position is start.
All right,
So now we can examine the other nodes or excuse me, the other vertices with the lowest cost.
So we will say while at some
state of cost position equals visited dot pop.
So now we need to check to see if the position we're at is the goal.
So if position is equal to our goal, then we just want to go ahead and return some cost.
And that cost is going to be our distance to get from our starting to our goal.
Otherwise, if our cost is greater than our current distance, well then we've already found a better
way.
So we can just go ahead and say continue.
And then otherwise, for each node that we can reach, we need to check to see if there is a way forward
with a lower cost going through that node.
So we can save for edge in our graph
with our current position.
Then we need to say next is equal to state cost of cost plus edge cost and position of edge node.
So if our next cost is less, so if next dot cost is less than our current dist next position.
Then we found a better way.
So we will say visited dot push next.
And now that we have found a better way, we will say dist next dot position is equal to next dot cost.
So that's all we need to do to implement the shortest path here, and we return none still down here.
In the event that there is no way for us to get from start to our goal.
So if we say get to some vertex that does not exist in the graph, then we want to return none because
we don't have a path to it.
So now we can test this out and we'll test this out by using the graph we created in our previous lecture.
That way we can very clearly identify if this is working or not.
So we will say mod test, use super on everything.
That way we can bring it all into scope and we will say Test
Dykstra.
And then here, now we can create our graph.
So we will say let graph is equal to a VEC.
And then inside of our vec we're going to have obviously another VEC and our vec is going to contain
an edge going from node one, cost six.
Vic?
Nope.
Excuse me.
Edge of Node two cost.
For.
And I need to add in that guy, Tim.
It helps if I add in everything appropriately.
There we go.
And we will add in one more edge of Node three.
Cost one.
Now we will add another vector and we can start copying and pasting.
To speed these up.
So this vector will go from node zero.
Two six.
And we will go from node to.
To three.
So what we're doing here again is we are recreating our graph from the previous lecture where we learned
to see how Dijkstra's algorithm worked.
So now we're going from Node 0 to 4, and I know we didn't have a Node zero in the previous lecture,
but remember, vertex indexes start at zero, so subtract one from all of our vertex nodes in the previous
lecture, so vertex one would become zero for text to becomes one, and so on and so forth.
We can let's go format this just to make it easier to read.
There we go.
All right.
So in our Node two, technically we go from zero from node 2 to 0 with a cost of four.
We go from.
To node one with a cost of three.
And remember, it's un directed.
So we want to make sure we have all of our edges going both ways.
And then we go to Node three with a cost of one.
And add a comma here.
And our last node.
We have our edge.
You don't need those.
Our edge going from zero to to zero with a cost of one and our other edge going to node two with a cost
of one as well.
So let's run cargo format again.
All right.
So that looks a lot better.
So what we have here is to make this clear, this is Node zero.
Node one.
No.
Two and Node three.
So here we have Node zero going to one with a cost of six, node zero going to two with a cost of four
0 to 3, with a cost of one, 1 to 0 cost of six.
So that way you can see that it is undirected, it is an undirected graph.
And again, this is the same exact graph that we did in our previous lecture.
So if you need a refresher on what this graph looks like visually, feel free to just to go rewatch
that lecture.
That way you can see what it looks like.
And so now we can say assert equals and we want to call
what did we call our function up here?
Shortest path.
So we say shortest path pass in our graph.
Our start we will say is zero.
And our goal is we want to get to Node one
and
Q So what we're expecting to be returned here is some five.
So if you remember from the previous lecture, our shortest path was one from starting from one to get
to two.
Our shortest path was one for three and then two to get to two, and our weight of that was one plus
one plus three.
So five.
So we're expecting some five to be returned here.
So if we test this, we see that that is the value that we were indeed returned.
So our Dijkstra's shortest path algorithm is working correctly.
So if you have any questions about this implementation, please feel free to ask them in the Q&A section
and in the next section, we will start looking at some algorithms that we can use when evaluating trees.