1
00:00:00,750 --> 00:00:01,510
Hi, everyone.

2
00:00:01,530 --> 00:00:07,590
So in this video, we are going to study another graph algorithm, and that is basically Dijkstra single

3
00:00:07,590 --> 00:00:09,850
source, shortest path algorithm.

4
00:00:10,800 --> 00:00:13,710
So why do we need Dijkstra algorithm?

5
00:00:13,710 --> 00:00:15,030
Advertisers use case.

6
00:00:15,060 --> 00:00:22,140
So what will happen is, given the starting node, so given the starting node, what do you need to

7
00:00:22,140 --> 00:00:25,360
find out the shortest distance to all the nodes, for example?

8
00:00:25,380 --> 00:00:28,180
I think the shortest distance to this node will not be seven.

9
00:00:28,710 --> 00:00:30,230
It will not be four plus two.

10
00:00:30,240 --> 00:00:33,630
It will be one plus one, two and two plus two four.

11
00:00:34,260 --> 00:00:34,670
Right.

12
00:00:34,830 --> 00:00:39,480
Similarly, the shortest part of this node will not be before it will be one plus one two.

13
00:00:40,560 --> 00:00:46,890
Similarly, the shortest route this node will be when given the source node, given the source node

14
00:00:46,890 --> 00:00:50,550
unit to find out the shortest path to all other nodes.

15
00:00:51,390 --> 00:00:54,370
So in this case, Dijkstra algorithm will help us.

16
00:00:55,140 --> 00:00:57,070
So how Dijkstra's algorithm works.

17
00:00:57,540 --> 00:01:04,379
So let's try to understand how it will find out the shortest path to all the nodes given a single node,

18
00:01:04,560 --> 00:01:04,870
OK.

19
00:01:05,190 --> 00:01:11,100
So in input, the input provided to us, the source node and the graph.

20
00:01:11,280 --> 00:01:16,410
So from the source node, I have to find the shortest path to all other nodes.

21
00:01:17,880 --> 00:01:18,950
So it's very simple.

22
00:01:19,260 --> 00:01:20,140
What do you need to do?

23
00:01:20,580 --> 00:01:25,860
So initially you will say the distance of node two source node will be zero.

24
00:01:26,010 --> 00:01:33,150
Right distance of this node from source node is initially infinity distance of this node from source

25
00:01:33,150 --> 00:01:38,340
nodes, initially infinity distance of this node from source and all this initial infinity.

26
00:01:38,580 --> 00:01:39,930
So one thing is very clear.

27
00:01:39,930 --> 00:01:45,690
We need one this that will maintain the distance from the node.

28
00:01:45,690 --> 00:01:47,480
So we need one distance density.

29
00:01:47,880 --> 00:01:48,330
Right.

30
00:01:48,570 --> 00:01:53,310
And to mark whether we have visited one node or not, we need one visitor at.

31
00:01:56,370 --> 00:02:06,180
Right, so let's see how it will work, so the distance of suicide note is zero, right?

32
00:02:06,510 --> 00:02:10,440
So what it will do so go to all the neighbors again.

33
00:02:10,590 --> 00:02:11,350
What will do?

34
00:02:11,370 --> 00:02:15,120
We will go to all neighbors.

35
00:02:17,320 --> 00:02:24,280
And the neighbors should not have been visited, go to all neighbors, which are not visited yet.

36
00:02:28,270 --> 00:02:29,170
Which are not.

37
00:02:30,850 --> 00:02:32,710
Visited yet.

38
00:02:34,930 --> 00:02:41,080
So we need to go to all the neighbors of these sorts of attacks, so it has this neighbor, it has this

39
00:02:41,080 --> 00:02:42,490
neighbor, it has this neighbor.

40
00:02:42,730 --> 00:02:44,260
So it has three neighbors.

41
00:02:44,680 --> 00:02:48,530
Let's start with the vortex to let's start with this neighbor.

42
00:02:48,910 --> 00:02:56,110
So what I'm going to do, zero plus seven is less than infinity.

43
00:02:57,100 --> 00:03:02,290
So zero is basically divide, not waste.

44
00:03:02,470 --> 00:03:03,820
It is basically distance.

45
00:03:05,650 --> 00:03:07,300
So distance of.

46
00:03:08,680 --> 00:03:22,840
Vertex, you, which is zero plus bit of vertex you v is less than distance of Vertex V in this case,

47
00:03:23,260 --> 00:03:34,540
what you're going to do is you will update that distance of V to basically distance off you, plus weight

48
00:03:35,230 --> 00:03:36,640
off you and V.

49
00:03:37,990 --> 00:03:40,590
So let me try to explain what is happening here.

50
00:03:41,950 --> 00:03:46,330
C distance of source node from source node will be zero.

51
00:03:46,750 --> 00:03:51,640
The distance of this noticiero zero distance of this node have not been calculated.

52
00:03:52,270 --> 00:03:55,900
Distance of this node from source node has not been calculated yet.

53
00:03:56,110 --> 00:04:01,330
So that's why distances infinity distance of this node has not been calculated from the source, nor

54
00:04:01,330 --> 00:04:01,980
as of yet.

55
00:04:02,200 --> 00:04:04,090
So that's why the distances infinity.

56
00:04:05,230 --> 00:04:12,580
Now, what I am doing here is distance of source node that is zero plus basically any vertex.

57
00:04:12,910 --> 00:04:15,730
So my distance plus this weight.

58
00:04:16,360 --> 00:04:22,430
So my distance which is zero plus this weight, which is seven is less than that distance of node two.

59
00:04:22,720 --> 00:04:27,540
So what I am going to do is I will update this, I will update this to Seven Network.

60
00:04:27,580 --> 00:04:39,520
I am writing here Abdeh to seven similarly my distance plus V, so my distance plus V is less than infinity

61
00:04:39,520 --> 00:04:42,010
distance of the vertex distance of my neighbor.

62
00:04:42,280 --> 00:04:46,270
So I will update this to zero plus four which is four.

63
00:04:47,200 --> 00:04:50,950
Similarly zero plus one is less than the distance.

64
00:04:51,190 --> 00:04:55,330
So I will update infinity to when I will change infinity to one.

65
00:04:56,810 --> 00:05:05,020
And similarly what will do will mark that the vertex has been visited and now what we need to do.

66
00:05:05,200 --> 00:05:11,460
So this vertex is the distance when this vertex has distance for this vertex has distance seven.

67
00:05:11,860 --> 00:05:18,370
So we need to pick the vertex, which has minimum distance since for this use case.

68
00:05:18,380 --> 00:05:24,670
What we can do, we can use minimum Hipp, we can use minimum Ahepe.

69
00:05:25,180 --> 00:05:26,020
So that will do.

70
00:05:26,020 --> 00:05:31,930
We will pick vertex, which has minimum distance.

71
00:05:33,810 --> 00:05:41,940
We will pick the vortex, which has minimum distance, so one, four and seven, I think one is a minimum

72
00:05:42,780 --> 00:05:43,230
rate.

73
00:05:43,230 --> 00:05:44,810
When is minimum so big one.

74
00:05:45,780 --> 00:05:53,270
So I am picking one and for one, nobody to do go to all these vortices, go to all the neighbors.

75
00:05:53,850 --> 00:05:55,380
So I will go to one.

76
00:05:55,560 --> 00:05:57,230
But one is visited.

77
00:05:57,240 --> 00:05:59,260
So this is Vertex 1.0.

78
00:06:00,130 --> 00:06:03,840
One is wasted, so do not go to Vortex three.

79
00:06:04,830 --> 00:06:08,220
So my distance is one which is one.

80
00:06:08,220 --> 00:06:11,760
So one plus one two is basically less than four.

81
00:06:12,060 --> 00:06:14,060
So an update to two.

82
00:06:14,380 --> 00:06:22,440
So my distance which is one word, which is also one is less then this distance which was four.

83
00:06:22,440 --> 00:06:29,820
So I am updating to two, so I will update four by two rate and four doesn't have any other neighbor

84
00:06:30,090 --> 00:06:31,700
and I have visited four.

85
00:06:32,160 --> 00:06:40,440
So let's marketers visited right now again from the minimum help pick the vertex which has the minimum

86
00:06:40,440 --> 00:06:40,920
distance.

87
00:06:41,280 --> 00:06:45,660
So this vertex has a distance to this vertex has a distance seven.

88
00:06:45,660 --> 00:06:49,710
So obviously I will pick three so big three and check.

89
00:06:50,190 --> 00:06:55,710
So visit Nabor Vertex one but it has already been visited.

90
00:06:56,160 --> 00:06:57,780
Go to this vertex.

91
00:06:57,780 --> 00:07:00,570
But this vertex has already been visited.

92
00:07:01,020 --> 00:07:07,020
Now go to Vertex to go to Vertex two because this has not been visited yet.

93
00:07:07,410 --> 00:07:07,650
No.

94
00:07:07,650 --> 00:07:11,370
Check my distances to the way it is two.

95
00:07:11,370 --> 00:07:17,130
So two plus two four four is less than seven since four is less than seven.

96
00:07:17,250 --> 00:07:19,380
So you will change it to four.

97
00:07:21,040 --> 00:07:28,450
And he doesn't have any other neighbor, so we have visited Vertex three now in the minimum.

98
00:07:28,720 --> 00:07:37,060
I have only one vertex with weight for so we will pick this vertex from the minimum hip and check.

99
00:07:37,450 --> 00:07:39,730
So this neighbor has been visited.

100
00:07:40,180 --> 00:07:42,300
This neighbor has also been visited.

101
00:07:42,580 --> 00:07:44,590
So I do not have any neighbor to visit.

102
00:07:44,950 --> 00:07:47,980
And I visited the north to visit Vortex two.

103
00:07:48,550 --> 00:07:50,080
So this is complete.

104
00:07:51,520 --> 00:08:00,430
And I know what is the minimum distance for all of them, so zero is the distance from the source node,

105
00:08:00,820 --> 00:08:01,600
which is correct.

106
00:08:02,050 --> 00:08:04,780
One is the distance from the source node.

107
00:08:04,780 --> 00:08:05,160
Right.

108
00:08:05,170 --> 00:08:08,710
One is the shortest distance, which is correct for three.

109
00:08:09,280 --> 00:08:12,600
Two is the minimum distance, which is correct.

110
00:08:12,820 --> 00:08:17,100
I will reach three via this way and not this way.

111
00:08:17,170 --> 00:08:18,300
Right this way.

112
00:08:18,310 --> 00:08:20,740
It was four and this way it was two.

113
00:08:20,890 --> 00:08:21,970
So it has two.

114
00:08:22,600 --> 00:08:30,760
Similarly for node to the minimum distance is basically for how far I will go via this.

115
00:08:31,510 --> 00:08:32,919
I will go wired this way.

116
00:08:33,700 --> 00:08:34,530
This is one.

117
00:08:35,470 --> 00:08:38,390
Then again, one and then two.

118
00:08:39,549 --> 00:08:39,980
Right.

119
00:08:40,179 --> 00:08:43,090
So the minimum distance will be four and not seven.

120
00:08:43,090 --> 00:08:47,260
I will not come by this way and I will also not come by this way forward.

121
00:08:47,260 --> 00:08:47,860
Plus two.

122
00:08:48,130 --> 00:08:50,230
I will come via this way when.

123
00:08:50,230 --> 00:08:52,200
Then one and then two.

124
00:08:52,540 --> 00:08:54,090
So that's why the distances four.

125
00:08:54,670 --> 00:08:57,190
So that's our Dijkstra algorithm works.

126
00:08:59,010 --> 00:09:02,650
Let me take one more example so that you can understand properly.

127
00:09:03,410 --> 00:09:03,820
Right.

128
00:09:06,670 --> 00:09:08,380
So this is basically a map.

129
00:09:10,480 --> 00:09:10,930
Right.

130
00:09:11,200 --> 00:09:20,150
The society is to be and these are the distance in kilometers, right, where they need to do from city.

131
00:09:21,520 --> 00:09:25,450
We need to find the shortest path to all of the cities.

132
00:09:26,000 --> 00:09:29,810
We need to find shortest path to all of the cities from city.

133
00:09:30,370 --> 00:09:34,000
So we will use Dijkstra algorithm for doing this again.

134
00:09:34,300 --> 00:09:35,180
What do we need to do?

135
00:09:35,440 --> 00:09:44,110
We need to maintain one visitor today and we need to maintain one this density and we need to maintain

136
00:09:44,110 --> 00:09:45,700
one heap, minimum heap.

137
00:09:45,700 --> 00:09:46,030
Right.

138
00:09:47,170 --> 00:09:48,640
We need to maintain one.

139
00:09:48,640 --> 00:09:50,710
Keep what I will do.

140
00:09:50,950 --> 00:09:54,490
Initially, the distance for safety will be zero.

141
00:09:55,030 --> 00:09:58,150
Vicenzo city from city will obviously be zero.

142
00:09:58,540 --> 00:10:04,810
And for the rest of the cities, the distance will be infinity because I have not calculated the distance

143
00:10:05,140 --> 00:10:05,990
as of now.

144
00:10:06,430 --> 00:10:11,600
So that's where the distance for all of the cities from Seoul's city is infinity.

145
00:10:12,520 --> 00:10:17,390
Now we're able to pick the vertex, which has the minimum distance.

146
00:10:17,410 --> 00:10:19,750
So this is distance zero Andrest.

147
00:10:20,500 --> 00:10:24,430
Every node, every vertex has distance infinity.

148
00:10:24,430 --> 00:10:26,920
So big zero go to all the neighbors.

149
00:10:27,580 --> 00:10:30,610
So zero plus four is less than infinity.

150
00:10:30,940 --> 00:10:36,940
So change it to four zero plus one is less than infinity.

151
00:10:37,450 --> 00:10:40,990
So zero plus one less than infinity to change it to when.

152
00:10:42,220 --> 00:10:45,020
And we have visited city.

153
00:10:48,300 --> 00:10:57,540
Now, out of four and one, which one is a minimum, one is minimum, so we will pick one so from one

154
00:10:57,870 --> 00:11:04,480
go to all the neighbors to go to neighbor a city, but it has already been visited.

155
00:11:05,140 --> 00:11:06,990
OK, go to City B..

156
00:11:07,290 --> 00:11:14,070
So one plus two, three three is less than four to change it to three.

157
00:11:16,260 --> 00:11:19,100
Similarly, this is another neighbor.

158
00:11:19,290 --> 00:11:26,250
So one plus one is less than infinity for change it to two, right.

159
00:11:26,550 --> 00:11:32,730
So my distance plus visit is less than your distance to change it to two.

160
00:11:32,910 --> 00:11:41,840
And now the CTF has been visited now from the minimum hip pick the city, which has the minimum distance.

161
00:11:42,120 --> 00:11:43,520
So this is three.

162
00:11:43,860 --> 00:11:44,910
This is infinity.

163
00:11:44,910 --> 00:11:45,870
This is infinity.

164
00:11:45,900 --> 00:11:47,490
This is too late.

165
00:11:47,880 --> 00:11:49,080
So this is minimum.

166
00:11:49,090 --> 00:11:57,990
So I will pick city before city go to all the neighbors city if my neighbor.

167
00:11:57,990 --> 00:11:59,830
But ATF has already been visited.

168
00:12:00,870 --> 00:12:02,040
Now go to city.

169
00:12:02,520 --> 00:12:07,140
So to my distances to where it is two kilometers.

170
00:12:07,350 --> 00:12:10,700
And this is Infinity's or two plus two for what is less than infinity.

171
00:12:11,040 --> 00:12:14,680
So change it to four thirty.

172
00:12:14,700 --> 00:12:17,360
It doesn't have any other neighbor.

173
00:12:17,370 --> 00:12:19,290
So city has been visited.

174
00:12:20,490 --> 00:12:23,100
Now this is for this is infinity.

175
00:12:23,520 --> 00:12:24,480
This is three.

176
00:12:24,720 --> 00:12:28,290
I will pick this city, this vertex.

177
00:12:28,770 --> 00:12:30,190
Go to all the neighbors.

178
00:12:30,690 --> 00:12:32,850
Neighbor has already been visited.

179
00:12:33,180 --> 00:12:35,630
Neighbor F has already been visited.

180
00:12:35,970 --> 00:12:37,280
Let's talk about neighbors.

181
00:12:37,300 --> 00:12:37,580
See.

182
00:12:37,980 --> 00:12:42,000
So my distance is three plus three plus eight.

183
00:12:42,000 --> 00:12:45,270
Eleven is less than infinity so change it to eleven.

184
00:12:46,680 --> 00:12:48,780
City B has now been visited.

185
00:12:50,250 --> 00:12:57,840
So now I have eleven and I have four in the heap so I will pick the minimum.

186
00:12:58,050 --> 00:13:01,980
Minimum is city B so big city D good.

187
00:13:02,020 --> 00:13:06,810
All the neighbors neighbor E has been visited so go to neighbor.

188
00:13:06,840 --> 00:13:12,060
See my distances for the visit is three to four plus three.

189
00:13:12,060 --> 00:13:19,470
Seven seven is less than eleven so change eleven to seven and now a city has been visited.

190
00:13:21,360 --> 00:13:26,280
Now let's talk about the last city in the heap.

191
00:13:26,280 --> 00:13:27,420
So this is the last city.

192
00:13:27,420 --> 00:13:31,170
So we'll pick this and our minimum here will become empty.

193
00:13:32,490 --> 00:13:34,860
So big this go to all the neighbors.

194
00:13:35,100 --> 00:13:40,110
So City B has already been visited, City D has already been visited.

195
00:13:40,380 --> 00:13:43,230
So I do not have any neighbor which is yet to be visited.

196
00:13:43,230 --> 00:13:44,160
So I am done.

197
00:13:44,400 --> 00:13:49,260
So I have visited City C and my hip is empty.

198
00:13:49,260 --> 00:13:54,810
So I will stop and I have minimum distances.

199
00:13:54,810 --> 00:13:57,240
I have the shortest path to all the cities.

200
00:13:57,510 --> 00:13:59,310
What is the shortest path so far?

201
00:13:59,310 --> 00:14:04,920
City be the shortest path history from city for city f.

202
00:14:04,920 --> 00:14:08,700
The shortest part is run from city four city.

203
00:14:08,700 --> 00:14:09,780
The shortest parties.

204
00:14:09,780 --> 00:14:15,380
Two shortest parties, four shortest parties, seven.

205
00:14:15,690 --> 00:14:19,590
Now let's check whether these spots are correct or not correct.

206
00:14:21,420 --> 00:14:26,430
So for city, distance from city to city will obviously be zero.

207
00:14:26,580 --> 00:14:27,540
So that is correct.

208
00:14:28,110 --> 00:14:31,890
So for City B, I am saying the minimum distance is three.

209
00:14:32,370 --> 00:14:37,290
How this distance can be achieved if I will go to City F and then go to this.

210
00:14:37,410 --> 00:14:39,540
So one place to three, which is correct.

211
00:14:40,410 --> 00:14:45,180
Let's talk about if so the minimum distance will be one km directly come to city STF.

212
00:14:45,450 --> 00:14:46,650
So one is correct.

213
00:14:47,850 --> 00:14:50,100
Let's struck our city city.

214
00:14:50,100 --> 00:14:55,980
The minimum distance I am saying is two and that will be correct because I will go to this, but this

215
00:14:55,980 --> 00:14:59,630
is one km again one km which is to correct.

216
00:15:00,150 --> 00:15:01,330
Let's roll call to duty.

217
00:15:01,380 --> 00:15:02,580
What will be the minimum.

218
00:15:02,880 --> 00:15:09,730
But so I am saying the minimum but minimum distance from city will be four by four because I will go

219
00:15:09,780 --> 00:15:13,890
at this way one km, one km again.

220
00:15:13,890 --> 00:15:17,850
So total two and this two kilometers are total four kilometers.

221
00:15:19,410 --> 00:15:22,360
Let's talk about the DC ACTC.

222
00:15:23,040 --> 00:15:26,460
I am saying the minimum kilometers, minimum distances seven.

223
00:15:26,910 --> 00:15:28,320
And what is the distance.

224
00:15:28,770 --> 00:15:35,730
This one only one km plus one km, which is two two plus two four and four plus three seven.

225
00:15:36,240 --> 00:15:43,020
Although there are many ways to reach the DC, I can compare this, but also four km plus eight km,

226
00:15:43,030 --> 00:15:46,800
but that will be twelve km and the minimum distance is seven.

227
00:15:46,800 --> 00:15:53,880
Similarly, I can come from this, but also that is one km plus two which is three km three plus eight

228
00:15:53,880 --> 00:15:55,380
again eleven kilometers.

229
00:15:55,710 --> 00:15:58,200
So the shortest parties, seven kilometers.

230
00:15:58,410 --> 00:16:04,470
And I have the shortest path stored in this distance area for every vertex, for every city.

231
00:16:05,010 --> 00:16:07,680
So that's how Dijkstra's algorithm works.

232
00:16:09,420 --> 00:16:13,590
So in next video, we will be writing the code for the Dijkstra's algorithm.

233
00:16:14,010 --> 00:16:14,910
So I will see you.

234
00:16:15,080 --> 00:16:17,630
The next one, so this is it in this video.

235
00:16:18,140 --> 00:16:18,680
Thank you.

