Hi, everyone.
So in this video, we are going to study another graph algorithm, and that is basically Dijkstra single
source, shortest path algorithm.
So why do we need Dijkstra algorithm?
Advertisers use case.
So what will happen is, given the starting node, so given the starting node, what do you need to
find out the shortest distance to all the nodes, for example?
I think the shortest distance to this node will not be seven.
It will not be four plus two.
It will be one plus one, two and two plus two four.
Right.
Similarly, the shortest part of this node will not be before it will be one plus one two.
Similarly, the shortest route this node will be when given the source node, given the source node
unit to find out the shortest path to all other nodes.
So in this case, Dijkstra algorithm will help us.
So how Dijkstra's algorithm works.
So let's try to understand how it will find out the shortest path to all the nodes given a single node,
OK.
So in input, the input provided to us, the source node and the graph.
So from the source node, I have to find the shortest path to all other nodes.
So it's very simple.
What do you need to do?
So initially you will say the distance of node two source node will be zero.
Right distance of this node from source node is initially infinity distance of this node from source
nodes, initially infinity distance of this node from source and all this initial infinity.
So one thing is very clear.
We need one this that will maintain the distance from the node.
So we need one distance density.
Right.
And to mark whether we have visited one node or not, we need one visitor at.
Right, so let's see how it will work, so the distance of suicide note is zero, right?
So what it will do so go to all the neighbors again.
What will do?
We will go to all neighbors.
And the neighbors should not have been visited, go to all neighbors, which are not visited yet.
Which are not.
Visited yet.
So we need to go to all the neighbors of these sorts of attacks, so it has this neighbor, it has this
neighbor, it has this neighbor.
So it has three neighbors.
Let's start with the vortex to let's start with this neighbor.
So what I'm going to do, zero plus seven is less than infinity.
So zero is basically divide, not waste.
It is basically distance.
So distance of.
Vertex, you, which is zero plus bit of vertex you v is less than distance of Vertex V in this case,
what you're going to do is you will update that distance of V to basically distance off you, plus weight
off you and V.
So let me try to explain what is happening here.
C distance of source node from source node will be zero.
The distance of this noticiero zero distance of this node have not been calculated.
Distance of this node from source node has not been calculated yet.
So that's why distances infinity distance of this node has not been calculated from the source, nor
as of yet.
So that's why the distances infinity.
Now, what I am doing here is distance of source node that is zero plus basically any vertex.
So my distance plus this weight.
So my distance which is zero plus this weight, which is seven is less than that distance of node two.
So what I am going to do is I will update this, I will update this to Seven Network.
I am writing here Abdeh to seven similarly my distance plus V, so my distance plus V is less than infinity
distance of the vertex distance of my neighbor.
So I will update this to zero plus four which is four.
Similarly zero plus one is less than the distance.
So I will update infinity to when I will change infinity to one.
And similarly what will do will mark that the vertex has been visited and now what we need to do.
So this vertex is the distance when this vertex has distance for this vertex has distance seven.
So we need to pick the vertex, which has minimum distance since for this use case.
What we can do, we can use minimum Hipp, we can use minimum Ahepe.
So that will do.
We will pick vertex, which has minimum distance.
We will pick the vortex, which has minimum distance, so one, four and seven, I think one is a minimum
rate.
When is minimum so big one.
So I am picking one and for one, nobody to do go to all these vortices, go to all the neighbors.
So I will go to one.
But one is visited.
So this is Vertex 1.0.
One is wasted, so do not go to Vortex three.
So my distance is one which is one.
So one plus one two is basically less than four.
So an update to two.
So my distance which is one word, which is also one is less then this distance which was four.
So I am updating to two, so I will update four by two rate and four doesn't have any other neighbor
and I have visited four.
So let's marketers visited right now again from the minimum help pick the vertex which has the minimum
distance.
So this vertex has a distance to this vertex has a distance seven.
So obviously I will pick three so big three and check.
So visit Nabor Vertex one but it has already been visited.
Go to this vertex.
But this vertex has already been visited.
Now go to Vertex to go to Vertex two because this has not been visited yet.
No.
Check my distances to the way it is two.
So two plus two four four is less than seven since four is less than seven.
So you will change it to four.
And he doesn't have any other neighbor, so we have visited Vertex three now in the minimum.
I have only one vertex with weight for so we will pick this vertex from the minimum hip and check.
So this neighbor has been visited.
This neighbor has also been visited.
So I do not have any neighbor to visit.
And I visited the north to visit Vortex two.
So this is complete.
And I know what is the minimum distance for all of them, so zero is the distance from the source node,
which is correct.
One is the distance from the source node.
Right.
One is the shortest distance, which is correct for three.
Two is the minimum distance, which is correct.
I will reach three via this way and not this way.
Right this way.
It was four and this way it was two.
So it has two.
Similarly for node to the minimum distance is basically for how far I will go via this.
I will go wired this way.
This is one.
Then again, one and then two.
Right.
So the minimum distance will be four and not seven.
I will not come by this way and I will also not come by this way forward.
Plus two.
I will come via this way when.
Then one and then two.
So that's why the distances four.
So that's our Dijkstra algorithm works.
Let me take one more example so that you can understand properly.
Right.
So this is basically a map.
Right.
The society is to be and these are the distance in kilometers, right, where they need to do from city.
We need to find the shortest path to all of the cities.
We need to find shortest path to all of the cities from city.
So we will use Dijkstra algorithm for doing this again.
What do we need to do?
We need to maintain one visitor today and we need to maintain one this density and we need to maintain
one heap, minimum heap.
Right.
We need to maintain one.
Keep what I will do.
Initially, the distance for safety will be zero.
Vicenzo city from city will obviously be zero.
And for the rest of the cities, the distance will be infinity because I have not calculated the distance
as of now.
So that's where the distance for all of the cities from Seoul's city is infinity.
Now we're able to pick the vertex, which has the minimum distance.
So this is distance zero Andrest.
Every node, every vertex has distance infinity.
So big zero go to all the neighbors.
So zero plus four is less than infinity.
So change it to four zero plus one is less than infinity.
So zero plus one less than infinity to change it to when.
And we have visited city.
Now, out of four and one, which one is a minimum, one is minimum, so we will pick one so from one
go to all the neighbors to go to neighbor a city, but it has already been visited.
OK, go to City B..
So one plus two, three three is less than four to change it to three.
Similarly, this is another neighbor.
So one plus one is less than infinity for change it to two, right.
So my distance plus visit is less than your distance to change it to two.
And now the CTF has been visited now from the minimum hip pick the city, which has the minimum distance.
So this is three.
This is infinity.
This is too late.
So this is minimum.
So I will pick city before city go to all the neighbors city if my neighbor.
But ATF has already been visited.
Now go to city.
So to my distances to where it is two kilometers.
And this is Infinity's or two plus two for what is less than infinity.
So change it to four thirty.
It doesn't have any other neighbor.
So city has been visited.
Now this is for this is infinity.
This is three.
I will pick this city, this vertex.
Go to all the neighbors.
Neighbor has already been visited.
Neighbor F has already been visited.
Let's talk about neighbors.
See.
So my distance is three plus three plus eight.
Eleven is less than infinity so change it to eleven.
City B has now been visited.
So now I have eleven and I have four in the heap so I will pick the minimum.
Minimum is city B so big city D good.
All the neighbors neighbor E has been visited so go to neighbor.
See my distances for the visit is three to four plus three.
Seven seven is less than eleven so change eleven to seven and now a city has been visited.
Now let's talk about the last city in the heap.
So this is the last city.
So we'll pick this and our minimum here will become empty.
So big this go to all the neighbors.
So City B has already been visited, City D has already been visited.
So I do not have any neighbor which is yet to be visited.
So I am done.
So I have visited City C and my hip is empty.
So I will stop and I have minimum distances.
I have the shortest path to all the cities.
What is the shortest path so far?
City be the shortest path history from city for city f.
The shortest part is run from city four city.
The shortest parties.
Two shortest parties, four shortest parties, seven.
Now let's check whether these spots are correct or not correct.
So for city, distance from city to city will obviously be zero.
So that is correct.
So for City B, I am saying the minimum distance is three.
How this distance can be achieved if I will go to City F and then go to this.
So one place to three, which is correct.
Let's talk about if so the minimum distance will be one km directly come to city STF.
So one is correct.
Let's struck our city city.
The minimum distance I am saying is two and that will be correct because I will go to this, but this
is one km again one km which is to correct.
Let's roll call to duty.
What will be the minimum.
But so I am saying the minimum but minimum distance from city will be four by four because I will go
at this way one km, one km again.
So total two and this two kilometers are total four kilometers.
Let's talk about the DC ACTC.
I am saying the minimum kilometers, minimum distances seven.
And what is the distance.
This one only one km plus one km, which is two two plus two four and four plus three seven.
Although there are many ways to reach the DC, I can compare this, but also four km plus eight km,
but that will be twelve km and the minimum distance is seven.
Similarly, I can come from this, but also that is one km plus two which is three km three plus eight
again eleven kilometers.
So the shortest parties, seven kilometers.
And I have the shortest path stored in this distance area for every vertex, for every city.
So that's how Dijkstra's algorithm works.
So in next video, we will be writing the code for the Dijkstra's algorithm.
So I will see you.
The next one, so this is it in this video.
Thank you.