1
00:00:00,990 --> 00:00:01,750
Hi, everyone.

2
00:00:01,770 --> 00:00:05,460
So in this video, we are going to write the call for the Dijkstra's algorithm.

3
00:00:05,490 --> 00:00:06,540
So let's start.

4
00:00:07,650 --> 00:00:10,920
So in the Dijkstra algorithm, what will be the input?

5
00:00:11,400 --> 00:00:14,570
So I think I will take two things as input.

6
00:00:14,580 --> 00:00:16,230
I will take what is the graph?

7
00:00:16,410 --> 00:00:22,110
And second thing is, I will take this also vertex, the source city, the city from which I have to

8
00:00:22,110 --> 00:00:24,240
find out the distance of all of the cities.

9
00:00:25,060 --> 00:00:25,350
Right.

10
00:00:25,770 --> 00:00:30,470
So the source of the graph and the source vertex.

11
00:00:31,080 --> 00:00:34,590
Now, what we need to do, as I told you, for each vertex.

12
00:00:36,690 --> 00:00:42,360
For each city, for each vertex, we what do we need to do?

13
00:00:44,820 --> 00:00:51,000
I will Mark visited as falls because currently I have not visited any of the city, any of the vertex.

14
00:00:51,870 --> 00:01:02,040
Similarly, that distance at a distance of all the vertex is initially infinity now for the source node.

15
00:01:02,470 --> 00:01:05,099
But I need to do so for the source node.

16
00:01:05,400 --> 00:01:12,470
Basically you will mark the distance distance of source node from itself will obviously be zero.

17
00:01:12,480 --> 00:01:12,790
Right.

18
00:01:13,220 --> 00:01:14,100
So sorry.

19
00:01:14,110 --> 00:01:17,070
This I want to write source here.

20
00:01:17,400 --> 00:01:22,020
Some distance off source node from itself will obviously be zero.

21
00:01:23,220 --> 00:01:23,680
Right.

22
00:01:24,270 --> 00:01:24,840
What else.

23
00:01:25,140 --> 00:01:25,890
What to do.

24
00:01:25,890 --> 00:01:29,910
We need to create a minimum heap now to create.

25
00:01:32,290 --> 00:01:38,200
Create minimum hip and let's say the name of the hip is cool and what they will do.

26
00:01:38,230 --> 00:01:40,030
You will push these sorts of attacks.

27
00:01:40,750 --> 00:01:46,000
So we are going to push you don't push the salsa vortex.

28
00:01:46,510 --> 00:01:48,730
So I am pushing the salsa vortex.

29
00:01:49,120 --> 00:01:50,980
And breast is pretty much simple.

30
00:01:52,010 --> 00:02:01,450
We decided that while the que is not empty, while my minimum hip is not empty, what we will do, we

31
00:02:01,450 --> 00:02:05,200
will pick, we will pick the minimum vertex.

32
00:02:05,770 --> 00:02:06,280
So.

33
00:02:08,259 --> 00:02:13,130
We will pick the minimum city minimum vortex.

34
00:02:13,480 --> 00:02:17,100
What do I mean by minimum vortex whose distances minimum?

35
00:02:17,620 --> 00:02:18,040
Right.

36
00:02:18,370 --> 00:02:24,960
So after picking this one to go to all the neighbors, so go to all the neighbors.

37
00:02:25,210 --> 00:02:37,750
So for each neighbor, for each neighbor, Vertex V of you, first of all, what do we need to check?

38
00:02:38,740 --> 00:02:43,040
We need to check whether the neighbor has been visited already or not visited.

39
00:02:43,600 --> 00:02:54,480
So if the neighbor is not visited, then only I will do something right.

40
00:02:54,730 --> 00:03:00,460
And one more thing that I forgot to do here is after picking the element from the minimum heap, we

41
00:03:00,460 --> 00:03:03,910
need to mark this vertex as visited.

42
00:03:04,330 --> 00:03:07,240
So visited of you is basically true.

43
00:03:07,690 --> 00:03:09,580
We have visited this vertex.

44
00:03:11,040 --> 00:03:17,940
So if the neighbor has not been visited, then only I will do something and I will do I will check if

45
00:03:17,940 --> 00:03:23,850
my distance, if my distance plus the word.

46
00:03:27,150 --> 00:03:31,170
Between you and me is less than your distance.

47
00:03:34,480 --> 00:03:42,010
If that is the case, then I am of going to update your distance so your distance should have been updated,

48
00:03:42,280 --> 00:03:49,040
some distance of me will be my distance, plus the distance between us.

49
00:03:49,060 --> 00:03:53,200
That is the word between us, the number of kilometers between us.

50
00:03:54,640 --> 00:03:57,580
And one more thing we need to push.

51
00:03:59,320 --> 00:04:01,870
We need to push this vortex inside.

52
00:04:01,870 --> 00:04:03,840
He also inside the medium also.

53
00:04:04,190 --> 00:04:10,260
So it could not push this vortex rate, could not push this vortex.

54
00:04:10,900 --> 00:04:17,260
So this if and this for loop ends here and this via loop answer and this function answer.

55
00:04:17,260 --> 00:04:22,180
And we are done and our code is ready.

56
00:04:22,780 --> 00:04:26,200
So this is the code for the Dijkstra algorithm.

57
00:04:26,770 --> 00:04:27,190
Right.

58
00:04:27,520 --> 00:04:31,240
If you have any doubt in this code, you can definitely ask me.

59
00:04:31,450 --> 00:04:33,570
This is the complete code for Dijkstra.

60
00:04:33,580 --> 00:04:35,470
So this is it from this device.

61
00:04:35,470 --> 00:04:37,100
I will see you in the next one.

62
00:04:37,180 --> 00:04:37,780
Thank you.