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.