In this lecture, we are going to go over Dijkstra's algorithm.
Dijkstra's algorithm is used to find the shortest path between nodes and a graph, which may represent,
for an example, something like a road network.
So let's build us out a simple graph here.
So we'll have Node one, two, three and four, and we'll connect one and two with six, two and three
with three, one and four with one or three and four with one and one and four with one.
And we will connect one and three with four.
So let's say we want to start out at Node one.
So we will say our starting vertex is one and we want to find the shortest path to three.
And well, this might be something that we obviously already kind of know how to do just by looking
at it.
But let's walk through it just to see what we can do for us to get to three.
Well, if we start at one, we see that we can go and let's say we'll have paths here.
So we start at one.
Let's say we go one, 2 to 3.
So one, two, three.
Well, that would be six plus three.
So our total weight for that would be nine.
Let's say we went one 4 to 3, that would be two.
And then the other one is 1 to 3.
Well, that would be four.
So obviously our answer to this would be two.
Well, what if we wanted to go 1 to 2 so we could go one, two, and that would equal six.
We could go 1 to 4 or excuse 1 to 4, and that equals one.
And then we can go 4 to 3 and that equals one.
And then we can go 3 to 2.
And that equals three.
So then we would be three plus one plus one and that equals five.
Our other option would be 1 to 3 and that equals four and then 3 to 2 and that equals three, which
equals seven.
So we know that one and two are out and now one, three, two is out.
So our shortest path for 1 to 2.
So from 1 to 2, our shortest path would be to one for
three two.
So that's basically how Dijkstra's algorithm works.
We are evaluating the weight of the edges between all the nodes, and we are going to evaluate all the
possible paths that we can have and determine which one has the lowest weight, and that will be the
most efficient path for us to take.
So in the next lecture, we're going to see what it looks like to implement Dijkstra's algorithm and
then run some test cases so that we can see it working in action.
If you have any questions about Dijkstra's algorithm and how it works, please feel free to ask me in
the Q&A section.