1
00:00:01,560 --> 00:00:02,280
Hi, everyone.

2
00:00:02,310 --> 00:00:09,030
So in this video, we are going to discuss about Prem's algorithm, Supreme's algorithm is another Iguanodon

3
00:00:09,030 --> 00:00:09,900
for finding out.

4
00:00:09,900 --> 00:00:14,900
Dominionist Manningtree, we have already discussed one algorithm which was kruskal to find out Dimino

5
00:00:14,910 --> 00:00:18,970
spanning three Brimson liver damage and other algorithm to find out the same.

6
00:00:18,970 --> 00:00:19,760
You spanning three.

7
00:00:20,100 --> 00:00:21,850
So given a graph, let's see.

8
00:00:22,800 --> 00:00:26,010
So this is the graph given to us and we want to find out the meaning spending.

9
00:00:26,520 --> 00:00:30,150
So how primps algorithm works is we basically do three things.

10
00:00:30,450 --> 00:00:32,060
For example, let me write here.

11
00:00:32,130 --> 00:00:33,660
What are all the vertex we have?

12
00:00:33,850 --> 00:00:37,320
So we have Vertex zero, one, two, three and four.

13
00:00:37,330 --> 00:00:37,770
Right.

14
00:00:37,990 --> 00:00:39,030
We have Vertex Zero.

15
00:00:39,030 --> 00:00:41,930
We have Vertex one, two, three and four.

16
00:00:42,510 --> 00:00:48,750
Now that think that we are to maintain our parent and build.

17
00:00:51,000 --> 00:00:58,440
And also, which Naude has been visited, so let's right here visited, which all we have visited as

18
00:00:58,440 --> 00:00:59,900
of now, right.

19
00:01:00,240 --> 00:01:04,860
So what we do is in PIMS algorithm, we can start from any node.

20
00:01:05,220 --> 00:01:09,050
So let's say this is my source note, this is my start node.

21
00:01:09,210 --> 00:01:13,050
So you can pick any node as the start node or the node.

22
00:01:13,350 --> 00:01:16,960
So since this is the source node, what I will do, I will assign it.

23
00:01:17,370 --> 00:01:22,850
So this has a big zero and list all the nodes has it infinity.

24
00:01:24,600 --> 00:01:29,180
So the word zero is picked up as the start node, the node.

25
00:01:29,490 --> 00:01:30,810
So it's worth zero.

26
00:01:31,840 --> 00:01:34,700
And the weight of rest of the nodes are infinity.

27
00:01:34,750 --> 00:01:36,460
This is the first thing that you need to do.

28
00:01:37,990 --> 00:01:40,750
Similarly, let's talk about parents.

29
00:01:40,930 --> 00:01:44,670
So what is the parent of zero, Norvan, minus one?

30
00:01:44,710 --> 00:01:48,540
Similarly, the parent of rest of the nodes are not determined yet.

31
00:01:48,820 --> 00:01:53,690
So the parent are minus one for all of the nodes so we can initialize these values.

32
00:01:53,950 --> 00:01:57,660
Similarly, I have not visited any of the node as of yet.

33
00:01:57,670 --> 00:02:03,050
So my visited arrays, basically my visitor site is basically empty right now.

34
00:02:03,070 --> 00:02:03,680
Let's start.

35
00:02:04,300 --> 00:02:06,310
So what I will do, I will start from the source node.

36
00:02:07,480 --> 00:02:08,740
I will start from this node.

37
00:02:08,740 --> 00:02:14,010
And what do we need to visit each and every node who are the neighbor of the Snowden.

38
00:02:14,320 --> 00:02:17,110
So we need to go to.

39
00:02:18,070 --> 00:02:20,410
We need to go to every neighbor.

40
00:02:23,040 --> 00:02:24,450
Every neighbor vertex.

41
00:02:25,800 --> 00:02:28,130
Which is not visited yet.

42
00:02:30,270 --> 00:02:33,900
Which is not visited.

43
00:02:35,800 --> 00:02:43,980
Right, we need to go to every neighbor vortex, which is not visited so far, zero Jike Vortex one

44
00:02:43,990 --> 00:02:48,810
has been visited or not visited that is empty and we are visiting the noticiero.

45
00:02:48,820 --> 00:02:53,200
So I will put Noticiero as this note has been visited.

46
00:02:53,410 --> 00:02:54,490
I am repeating myself.

47
00:02:54,490 --> 00:02:58,030
I am standing at this node, so I am visiting this node.

48
00:02:58,360 --> 00:03:05,050
So in the visitor, that zero node has been the vortex, zero has been visited and now I am taking its

49
00:03:05,050 --> 00:03:06,430
neighbor to Vertex.

50
00:03:06,430 --> 00:03:07,360
One has been visited.

51
00:03:07,360 --> 00:03:07,890
Are not.

52
00:03:07,900 --> 00:03:09,990
No Vertex one has not been visited.

53
00:03:10,600 --> 00:03:13,930
So what I will do, I will compare this thing forward and infinity.

54
00:03:14,560 --> 00:03:18,910
So four is less than infinity so I will update this to four.

55
00:03:19,390 --> 00:03:24,820
So what I am taking here, I am checking this distance so I am checking the distance.

56
00:03:25,980 --> 00:03:35,540
Veered between the Vortex zero and one, since the world is less than the weight of Vortex one, so

57
00:03:35,550 --> 00:03:37,860
the weight of Vortex one was infinity.

58
00:03:38,700 --> 00:03:43,950
So I will update infinity before I will replace infinity by a four to four vortex.

59
00:03:43,950 --> 00:03:50,190
When the new world is full and with the parent, I am coming from vortex to zero.

60
00:03:50,190 --> 00:03:57,710
So Vortex zero is deeper and zero has one more neighbor, which is neighbor two, vortex two.

61
00:03:59,070 --> 00:04:00,480
So this is it.

62
00:04:00,480 --> 00:04:01,800
And this is infinity.

63
00:04:02,100 --> 00:04:03,840
So it is less than infinity.

64
00:04:04,020 --> 00:04:07,700
So I will replace infinity by eight, right.

65
00:04:07,710 --> 00:04:09,360
I will replace infinity by eight.

66
00:04:09,690 --> 00:04:12,840
So replace infinity, replace weird by it.

67
00:04:12,840 --> 00:04:16,800
And with the parent for Vortex zero I am coming from Vortex zero.

68
00:04:17,490 --> 00:04:20,519
So the parent for Vortex two is vortex zero.

69
00:04:20,880 --> 00:04:21,420
Simple.

70
00:04:21,839 --> 00:04:24,200
Now Zero doesn't have any other neighbor.

71
00:04:25,470 --> 00:04:31,590
So since zero doesn't have any other neighbor now what will do, pick the node which has the minimum

72
00:04:31,590 --> 00:04:31,850
wage.

73
00:04:32,340 --> 00:04:33,330
So what I need to do.

74
00:04:35,410 --> 00:04:36,550
Big Naude.

75
00:04:39,000 --> 00:04:40,200
Which has.

76
00:04:43,270 --> 00:04:44,060
Minimum wage.

77
00:04:45,910 --> 00:04:52,200
So initially, this node was having a bit of zero and list, all the nodes were having weird infinity.

78
00:04:52,720 --> 00:04:55,650
That's why I paid so snoad simple.

79
00:04:56,020 --> 00:05:00,030
Now I have four nodes left for two, three and four.

80
00:05:00,040 --> 00:05:06,650
Let me right here, big node, which has minimum wage and is not visited yet and not visited.

81
00:05:08,290 --> 00:05:13,830
So currently I have visited only one node, only one vertex for Vertex.

82
00:05:13,870 --> 00:05:14,960
Still need to be visited.

83
00:05:14,980 --> 00:05:21,360
So this vertex has a way to for this vertex as a weight of infinity, this infinity and this it.

84
00:05:21,610 --> 00:05:25,150
So I think this is the minimum rate where it is minimum for this.

85
00:05:25,160 --> 00:05:26,460
So I will visit one.

86
00:05:27,160 --> 00:05:28,210
Let's visit one.

87
00:05:30,880 --> 00:05:32,890
So I am visiting one.

88
00:05:35,860 --> 00:05:40,840
Who all our neighbors are often right, we need to go to neighbors zero, his neighbor, but zero is

89
00:05:40,840 --> 00:05:46,160
already visited, so we will not visit zero to his neighbor made to his neighbor.

90
00:05:46,360 --> 00:05:50,460
So this is to this is it, too, is less than it's the place.

91
00:05:51,220 --> 00:05:52,750
So for what?

92
00:05:52,760 --> 00:05:54,490
Next to the new realities, too.

93
00:05:54,760 --> 00:05:58,570
And this word is coming from vortex one.

94
00:05:59,920 --> 00:06:04,180
One has a neighbor to this very day six, this world is infinity.

95
00:06:04,180 --> 00:06:05,830
Replace infinity by six.

96
00:06:06,350 --> 00:06:09,070
Replace infinity by six.

97
00:06:09,070 --> 00:06:10,660
Who is the parent for Vertex three.

98
00:06:10,960 --> 00:06:12,580
I am coming from Vertex one.

99
00:06:12,820 --> 00:06:14,170
So parent is Vertex one.

100
00:06:14,680 --> 00:06:16,240
One doesn't have any other neighbor.

101
00:06:16,510 --> 00:06:16,880
Good.

102
00:06:17,470 --> 00:06:25,630
So now again pick the node which has the minimum wage and is not visited.

103
00:06:25,630 --> 00:06:30,430
So I have three nodes which are yet to be visited two, three and four.

104
00:06:30,430 --> 00:06:32,740
So this has a weight of to this as a bit of sex.

105
00:06:32,780 --> 00:06:34,210
This has a word of infinity.

106
00:06:34,480 --> 00:06:36,280
So lets visit to write.

107
00:06:39,070 --> 00:06:46,000
So big Danovitch, which has been Vertex two, has been made and it is not visited yet, so let's visit

108
00:06:46,000 --> 00:06:46,630
this node.

109
00:06:49,300 --> 00:06:54,520
So go to all the neighbors, go to all the neighbors of the two has a neighbor, one, but one has been

110
00:06:54,520 --> 00:07:00,910
visited too, has a neighbor zero but zero is also visited to his neighbor.

111
00:07:00,910 --> 00:07:05,670
Three three is not visited yet and three is less than six.

112
00:07:06,310 --> 00:07:08,740
So update the with the history.

113
00:07:08,980 --> 00:07:10,800
Let's update this to three.

114
00:07:11,620 --> 00:07:13,390
And who is the parent of three.

115
00:07:13,840 --> 00:07:15,730
Parent of three is vertex to.

116
00:07:17,390 --> 00:07:25,790
Similarly, the six nine nine is less than infinity, so replace infinity by nine, so replace infinity

117
00:07:26,060 --> 00:07:26,830
by nine.

118
00:07:26,840 --> 00:07:28,430
And who is the parent for Vertex?

119
00:07:28,430 --> 00:07:31,820
For Vertex two is the parent.

120
00:07:33,110 --> 00:07:36,030
Now, two doesn't have any other neighbor, right?

121
00:07:36,320 --> 00:07:43,940
So what we will do again, we will again pick the node, which has the minimum of it and is not visited.

122
00:07:44,480 --> 00:07:47,290
So I have to vertex left three and four.

123
00:07:47,690 --> 00:07:52,610
So these vertex has not been visited and out of them, this has less.

124
00:07:52,640 --> 00:07:53,570
Wait, wait.

125
00:07:53,960 --> 00:07:55,570
This has less it.

126
00:07:55,580 --> 00:07:56,810
So I will pick this.

127
00:07:56,820 --> 00:07:57,860
I will visit this.

128
00:07:58,640 --> 00:08:00,060
So let's visit this.

129
00:08:00,080 --> 00:08:02,860
So this will be zero one, two and three.

130
00:08:04,130 --> 00:08:07,330
So after picking the node, what are we doing?

131
00:08:07,340 --> 00:08:09,020
We are going to every neighbor.

132
00:08:09,290 --> 00:08:11,420
So good to neighbor when.

133
00:08:11,420 --> 00:08:13,100
But this neighbor has been visited.

134
00:08:13,490 --> 00:08:14,660
Go to neighbor too.

135
00:08:15,110 --> 00:08:17,000
But this neighbor has been visited.

136
00:08:17,270 --> 00:08:22,040
So go to this neighbor neighborhood and check this value.

137
00:08:22,430 --> 00:08:27,320
Wait, what we are doing, we are going to each and every neighbor vertex and we are checking this.

138
00:08:28,110 --> 00:08:29,770
So here we do.

139
00:08:29,780 --> 00:08:30,160
We have.

140
00:08:30,170 --> 00:08:33,080
So this is five, five, ten, nine.

141
00:08:33,260 --> 00:08:37,880
So replace nine by five, so replace nine by five.

142
00:08:38,270 --> 00:08:45,500
And who is the parent sole parent updater to Vertex three three does doesn't have any other neighbor.

143
00:08:46,010 --> 00:08:49,910
So good bye now pick the node which has not been visited.

144
00:08:49,910 --> 00:08:52,400
So there is only one node which has not been visited yet.

145
00:08:52,670 --> 00:08:58,820
So let's pick this node, let's pick this node and this will be able to answer that zero one, two,

146
00:08:58,820 --> 00:08:59,630
three and four.

147
00:09:00,530 --> 00:09:07,250
And now what we need to do is go to every neighbor vertex, which is not visited so far, has this neighbor.

148
00:09:07,250 --> 00:09:10,880
But this has visited this vertex, his neighbor.

149
00:09:10,880 --> 00:09:14,210
But this has also visited four doesn't have any other neighbor.

150
00:09:14,210 --> 00:09:15,110
So we will stop.

151
00:09:15,560 --> 00:09:19,850
So we will stop and how our spending tree will look like.

152
00:09:20,360 --> 00:09:21,350
So this is zero.

153
00:09:22,340 --> 00:09:22,850
Right.

154
00:09:23,150 --> 00:09:25,580
And how do we figure out the edges?

155
00:09:26,060 --> 00:09:30,290
So see, let me write the node first zero one to.

156
00:09:32,160 --> 00:09:33,480
Three and four.

157
00:09:35,770 --> 00:09:43,420
And let's show the value for zero, I have it zero for one, I have it for four when I have it four

158
00:09:43,810 --> 00:09:45,340
four two, I have two.

159
00:09:47,080 --> 00:09:49,180
For three, I have a weight of three.

160
00:09:50,620 --> 00:09:58,540
ForFour, I have a very tough life and what are the connections so zero is not coming from anywhere.

161
00:09:58,570 --> 00:10:03,090
One is coming from zero, so one is coming from zero for two.

162
00:10:03,370 --> 00:10:07,690
I am coming from one to four to I am coming from one, four, three.

163
00:10:07,690 --> 00:10:08,820
I am coming from two.

164
00:10:09,070 --> 00:10:15,100
So for three I am coming from two four, four, I am coming from three to four.

165
00:10:15,310 --> 00:10:16,540
I am coming from three.

166
00:10:16,720 --> 00:10:20,050
So this is your minimum spanning three.

167
00:10:22,330 --> 00:10:25,570
This is your spending tree and what is the total cost?

168
00:10:26,050 --> 00:10:27,250
What is the total weight?

169
00:10:27,370 --> 00:10:31,180
So you can add all these value zero four to three and five.

170
00:10:31,600 --> 00:10:36,870
So zero plus four plus two plus three plus five.

171
00:10:37,090 --> 00:10:40,230
So this is the minimum cost, right?

172
00:10:40,510 --> 00:10:43,360
This is the minimum wage and this is your minimum spending.

173
00:10:43,480 --> 00:10:43,760
Three.

174
00:10:45,730 --> 00:10:46,300
Simple.

175
00:10:47,750 --> 00:10:49,820
So that's how you can solve this problem.

176
00:10:49,850 --> 00:10:51,560
That's how TPIMs algorithm works.

177
00:10:51,980 --> 00:10:53,390
So can we write the algorithm?

178
00:10:53,510 --> 00:10:56,930
So writing the algorithm is very simple, what we are doing here.

179
00:10:56,960 --> 00:11:00,530
So we are picking every node which has the minimum wage.

180
00:11:00,650 --> 00:11:03,800
So for this thing, what we can do, we can use a minimum heap.

181
00:11:03,800 --> 00:11:04,160
Right.

182
00:11:05,170 --> 00:11:10,320
We can use a minimum for this because each time we need to pick the node which has the minimum wage.

183
00:11:10,700 --> 00:11:13,850
So it will insert all the witnesses in the heap.

184
00:11:13,850 --> 00:11:19,430
And each time we will pick out the vertex, which has the minimum value, minimum wage, and then we

185
00:11:19,430 --> 00:11:21,920
are going to every neighbor which is not visited.

186
00:11:22,070 --> 00:11:27,770
And for every neighbor, we are checking this condition and we are updating the value of it accordingly.

187
00:11:27,830 --> 00:11:29,360
Similarly, we are updating the parent.

188
00:11:29,750 --> 00:11:34,390
So let let us write the code for this algorithm, which is going to be very, very simple.

189
00:11:34,970 --> 00:11:35,450
So.

190
00:11:37,470 --> 00:11:43,750
So this primps algorithm will take Gadhafi's input and it will also take this starting nor the source

191
00:11:43,770 --> 00:11:44,040
code.

192
00:11:44,280 --> 00:11:45,200
So it doesn't matter.

193
00:11:45,210 --> 00:11:47,500
You can give any node as the source node.

194
00:11:48,870 --> 00:11:55,020
Now, first of all, we need to initialize theories visited at your parent data and your.

195
00:11:56,310 --> 00:11:57,930
So what we need to do.

196
00:11:59,170 --> 00:12:00,760
For each vertex.

197
00:12:03,170 --> 00:12:10,070
For each Vertex V word will be the value of parent, every parent of every node.

198
00:12:11,670 --> 00:12:12,340
Minus one.

199
00:12:13,380 --> 00:12:18,340
Similarly, the weights of every node is infinity.

200
00:12:19,290 --> 00:12:25,710
Similarly, no one has been visited as of yet, so visited of nor will be false.

201
00:12:26,370 --> 00:12:31,270
I have not listed any node, any vertex as of now, next.

202
00:12:31,320 --> 00:12:32,790
But we need to do so.

203
00:12:32,790 --> 00:12:33,690
We need to.

204
00:12:35,860 --> 00:12:39,370
We need to change the weight value for those.

205
00:12:41,670 --> 00:12:48,090
Right, so as discussed, the weight of Solis A. is going to be zero.

206
00:12:49,570 --> 00:12:53,650
What else do we need to do, one more thing as discussed.

207
00:12:53,900 --> 00:12:58,170
We need to insert all the vertex in the minimum rate.

208
00:12:58,510 --> 00:12:59,980
So what will do?

209
00:13:01,430 --> 00:13:06,170
Let me right here, so we will create create a minimum EHP.

210
00:13:09,160 --> 00:13:12,940
Create a minimum heap of all Devadas.

211
00:13:16,320 --> 00:13:24,600
Right, we will insert all the verdicts in the minimum so that we can get the minimum noad every time

212
00:13:25,110 --> 00:13:27,640
the not having the least value of it.

213
00:13:28,050 --> 00:13:29,640
So what they need to do while.

214
00:13:32,670 --> 00:13:39,200
While my priority queue, let's name it, to create a minimum help, create a minimum, help you, right.

215
00:13:39,570 --> 00:13:45,780
So while the queue is not empty, so while the queue is not empty.

216
00:13:47,600 --> 00:13:48,270
What we do.

217
00:13:48,870 --> 00:13:56,270
Pick the minimum load, so pick the minimum load, extract minimum.

218
00:13:57,720 --> 00:14:05,740
All right, we will get the minimum vortex, the vortex, having the least value of it, and now we

219
00:14:05,740 --> 00:14:07,290
need to visit all the neighbors.

220
00:14:08,080 --> 00:14:11,010
One more thing, since we are going to visit this node.

221
00:14:11,020 --> 00:14:14,380
So I need to change its value.

222
00:14:14,380 --> 00:14:19,000
To visit it of you is basically true.

223
00:14:19,010 --> 00:14:25,900
Now we are visiting this node, so I am setting the value visited of you to be true and go to every

224
00:14:25,900 --> 00:14:30,100
neighbor, go to every neighbor, which is not visited for each neighbor.

225
00:14:34,300 --> 00:14:35,740
For each neighbor, we.

226
00:14:37,210 --> 00:14:39,220
Of vortex you.

227
00:14:41,470 --> 00:14:47,500
What do you will do, first of all, this knowledge should not be wasted, so if the visited.

228
00:14:50,010 --> 00:14:54,060
If the neighbor has not been visited.

229
00:14:56,820 --> 00:15:03,540
If the neighbor has not been visited, then only I will check that condition, that if the distance

230
00:15:04,320 --> 00:15:18,540
if the if the if the distance between the vertex you and V is less, then the weight, the weight of

231
00:15:18,540 --> 00:15:19,380
Vertex V..

232
00:15:20,890 --> 00:15:28,720
If this is the case, then you will update Vertov V to be the distance.

233
00:15:30,460 --> 00:15:37,120
Between the vortex you and envy, and also you need to update the patent area.

234
00:15:37,420 --> 00:15:42,550
So now the parent of V is you Vertex U.

235
00:15:44,030 --> 00:15:44,830
And that's it.

236
00:15:49,060 --> 00:15:51,910
So that is the complete primps and you go out to them.

237
00:15:54,100 --> 00:15:55,610
I'm explaining it one more time.

238
00:15:55,630 --> 00:15:58,960
Let's take one more example, let's take that example only.

239
00:15:58,960 --> 00:15:59,280
Right?

240
00:16:00,250 --> 00:16:03,890
So I have so I have this zero.

241
00:16:05,200 --> 00:16:13,510
This was I think when this was I think to this was three and this was four.

242
00:16:16,170 --> 00:16:17,880
And we have these connections.

243
00:16:23,300 --> 00:16:25,420
So this was for this was it?

244
00:16:25,610 --> 00:16:28,550
This was to this was six.

245
00:16:28,580 --> 00:16:30,060
This was three.

246
00:16:30,890 --> 00:16:32,030
This was nine.

247
00:16:32,570 --> 00:16:33,770
And this was five.

248
00:16:34,700 --> 00:16:35,060
Right.

249
00:16:35,690 --> 00:16:38,960
So for every vertex parent is minus one.

250
00:16:39,200 --> 00:16:40,370
It is Infinity Vista.

251
00:16:40,370 --> 00:16:40,900
This falls.

252
00:16:41,810 --> 00:16:42,160
Right.

253
00:16:42,380 --> 00:16:44,540
So let me read the vortex here.

254
00:16:46,220 --> 00:16:48,020
Let me read it here.

255
00:16:50,090 --> 00:16:55,160
Let me read it here and let me write visited here.

256
00:16:58,160 --> 00:17:02,830
And this is my priority dequeue, this is to minimum, right?

257
00:17:03,620 --> 00:17:04,450
This is empty.

258
00:17:05,060 --> 00:17:13,520
So initially no one is visited so empty and I initialised parent to mind this one for all world is so

259
00:17:13,520 --> 00:17:14,210
vertex zero.

260
00:17:14,210 --> 00:17:14,810
Vertex one.

261
00:17:14,810 --> 00:17:15,470
Vertex two.

262
00:17:15,859 --> 00:17:17,310
Vertex three and Vertex four.

263
00:17:17,569 --> 00:17:18,650
So parent minus one.

264
00:17:18,650 --> 00:17:19,130
Minus one.

265
00:17:19,130 --> 00:17:19,730
Minus one.

266
00:17:20,180 --> 00:17:22,069
Minus one and minus one.

267
00:17:23,109 --> 00:17:24,890
Wait, let's talk about it.

268
00:17:24,890 --> 00:17:27,440
So weird initially infinity for all of them.

269
00:17:27,859 --> 00:17:28,680
So weird initially.

270
00:17:28,700 --> 00:17:29,960
Infinity for all of them.

271
00:17:32,300 --> 00:17:40,190
Since zero is the starting, not zero is the starting node, so it is changed to zero, so where it

272
00:17:40,190 --> 00:17:44,180
is changed to zero for this Andrest, everyone has a weird infinity.

273
00:17:46,250 --> 00:17:51,870
Then we are creating a minimum heap of all the witnesses, so push all the verdicts in the minimum heap

274
00:17:52,250 --> 00:17:55,280
so Vertex Zero has a weight of zero.

275
00:17:56,270 --> 00:18:03,820
Similarly, Vertex one has a weight of infinity vertex to infinity with vertex three infinity weight

276
00:18:04,310 --> 00:18:06,060
and vertex for infinity weight.

277
00:18:06,360 --> 00:18:07,640
This is your priority queue.

278
00:18:07,940 --> 00:18:12,770
Then what we are doing while the priority queue is not empty, while it is containing elements, you

279
00:18:12,770 --> 00:18:15,180
need to pick the minimum element each time.

280
00:18:15,200 --> 00:18:17,800
So this is the minimum bid.

281
00:18:17,810 --> 00:18:18,890
So I will pick this.

282
00:18:19,370 --> 00:18:20,810
So remove from the priority.

283
00:18:20,820 --> 00:18:24,010
You make the wisdom to be true.

284
00:18:24,530 --> 00:18:29,900
So zero has been visited, right, for all the numbers.

285
00:18:30,590 --> 00:18:33,950
So zero has number one and two for all the numbers.

286
00:18:33,950 --> 00:18:38,030
If they are not listed, one and two are not listed, check the distance.

287
00:18:38,330 --> 00:18:43,070
So distances four and four of the distances infinity.

288
00:18:43,070 --> 00:18:44,630
The four is less than infinity.

289
00:18:45,170 --> 00:18:46,550
Then you will update it.

290
00:18:46,850 --> 00:18:54,050
So update the word for vertex one to be four because distance four is less than with infinity.

291
00:18:54,350 --> 00:18:58,100
And also the parent, the parent will be updated to zero.

292
00:18:58,910 --> 00:19:03,140
Right now, again, I have one more number, which is number two.

293
00:19:03,440 --> 00:19:06,950
So distance eight is less than infinity distance.

294
00:19:06,950 --> 00:19:08,450
It is less than infinity.

295
00:19:08,450 --> 00:19:16,640
So so update the word here, update devilled here, then update the parent, which is Vertex zero.

296
00:19:17,240 --> 00:19:17,690
Right.

297
00:19:17,840 --> 00:19:19,700
And also you need to update here.

298
00:19:20,120 --> 00:19:27,110
So for infinity now, this has been updated to four and this infinity has been changed to it.

299
00:19:28,460 --> 00:19:33,050
Right now, Vertex Zero has visited all the neighbors.

300
00:19:33,650 --> 00:19:35,450
So I will come out of this for loop.

301
00:19:37,090 --> 00:19:42,500
I am going to come out of this for loop, and again, I will pick the minimum value from the priority.

302
00:19:42,560 --> 00:19:45,820
You know, the minimum is for eight infinity infinity.

303
00:19:46,030 --> 00:19:47,410
So this is minimum rate.

304
00:19:47,410 --> 00:19:51,280
So remove this and visit this 081.

305
00:19:51,910 --> 00:19:54,100
So you will visit this rate.

306
00:19:54,550 --> 00:19:57,490
You will make the true go to all the neighbors of one.

307
00:19:57,790 --> 00:19:59,260
So I will go to zero.

308
00:19:59,260 --> 00:20:05,770
But zero has already been visited, so zero is visited now go to two, two is not visited.

309
00:20:05,980 --> 00:20:10,900
So this distance too is less than eight distance too is less than eight.

310
00:20:11,170 --> 00:20:13,060
So you will update the IT and the parent.

311
00:20:13,330 --> 00:20:21,910
So you will update the will to be too and you will update the parent to be when similarly for three

312
00:20:23,020 --> 00:20:30,810
distance is six less than infinity support six here but six here change parent to one.

313
00:20:31,840 --> 00:20:36,910
So when I visited all the nodes I will come out of the for loop again.

314
00:20:36,910 --> 00:20:40,270
We will pick the minimum, we will make the visit to be true.

315
00:20:40,450 --> 00:20:42,820
Go to all the neighbors and the neighbor.

316
00:20:42,820 --> 00:20:46,400
If not visited, then check the distance between them and the visit.

317
00:20:46,660 --> 00:20:50,890
Every distance is less than the visit then of their parent and their child.

318
00:20:50,890 --> 00:20:52,260
This algorithm will work.

319
00:20:53,080 --> 00:20:56,110
So this is the code for the algorithm.

320
00:20:56,110 --> 00:21:00,460
So if you have any doubt in its algorithm, you can definitely ask me in the Q&A section.

321
00:21:00,640 --> 00:21:02,110
So this is it in this video.

322
00:21:02,320 --> 00:21:03,850
I will see you in the next one.

323
00:21:04,150 --> 00:21:04,750
Thank you.

