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.