🚀 Add to Chrome – It’s Free - YouTube Summarizer
00:00
hey everyone welcome back to the channel i hope you guys are doing extremely well so today we will be solving the problem shortest path in undirected graph having a unit distance so you will be given an undirected graph having unit weight
00:15
means the edge weights will be one now you need to find the shortest distance from a given source they'll also be giving you a source to all the points you have to find the shortest distance and if the path is not possible then you need to put something
00:32
like a minus one so that is what you need to do so assume that this is the particular given graph and this is the adjacency list of this given graph and i am telling you that hey listen uh the source is zero in this case so from zero if i ask
00:47
you what is the distance to one you will say the distance is one if i ask you from zero what is the distance to two you will say that this is the distance two so from zero if i ask you what is the resistance to six maybe like this is the shortest distance three so this is what you have to find from zero to all
01:04
the given notes you have to find me the shortest distance so how will we find the shortest path now we will be applying a plane bfs algorithm how i'll tell you that so in the bfs algorithm we'll start off with the queue data structure and we will store
01:20
the node in the first place and the distance so we'll be storing pairs in the queue data structure a plain q data structure so since the source is given as 0 what we do is we insert 0 comma 0 y 0 comma 0 because you know the distance
01:36
taken to reach 0 from 0 will be zero right that is what we will store in the queue initially right next we will be declaring a distance array of what size you see the number of nodes is eight so make sure you declare such a size that
01:51
you can fit in the index 8 as well so we'll be declaring a distance array of size 9 over here so that we can fit in the index 8 now all the places should be filled up with infinity you can take a very big number which cannot be your answer very very big
02:07
number what i've done is i'll be taking it as infinity and remember whatever source you are starting off with just make sure you assign it with distance 0 just make sure you rewrite infinity to distance 0 now let's quickly start the algorithm
02:23
so initially whatever is in the queue just take it out and you say okay initially i have a node 0 and i have a distance 0 as well now what i will do is for the node 0 i'll try to figure out who are the adjacent nodes and i see 1
02:38
is one of the adjacent nodes and 3 is one of the adjacent nodes so node 0 can go to a node which is 1 and it can also go to a node which is 3 that can be easily uh you can easily get one and three from the adjacency list now tell
02:53
me one thing if you are at node zero and the distance taken is zero and if you are trying to go to node one and you know that all these edges are having unique widths all these edges are having unit wet so can i say if this is taking a distance
03:10
one and previously it was distance zero this will be nothing but distance one can i see this in order to reach node one you will be ending up to take distance one so what you will do is you will go to node one and you will say previously what distance did i take
03:26
infinity it means you never reached here so now you are reaching with a distance one so what you will do is you will say okay now i'm reaching with a distance one so can you please replace this with a distance one and can you take this node one with the distance one and put that into the q data structure similarly
03:42
this will also be distance one because if you have taken distance 0 to reach node 0 from here a unit weight will take it to distance 1 so next you'll say 3 you are taking a distance 1 and node 3 with a distance 1 will be put into the
03:57
queue next i can see the task of this one is done and you'll move to the next node which is the next node it's one so i'll say node one has taken a distance of one what does this signify this signifies in
04:13
order to reach from the source to the node one i have consumed a distance of one i've consumed a distance of one now node one has adjacent nodes are zero two three that has three adjacent nodes node 0
04:29
it has node 2 it has node 3. again you can figure these things out from the adjacency list so i know this will be a plus 1 this will be a plus 1 this will be a plus 1 if i consider about distances because those are unique widths uh so if i see
04:44
the distance previously is one now the distance will be two so in order to reach node zero the distance is two but i have already reached here at a distance zero do i consider this the answer to that will be no you don't need to take a smaller distance because we are looking for
05:00
shortest spots next what i'll do is i'll go to this one and i'll say how much is the distance to so let's see for node 2 availability so i can reach it at a distance of two so node two at a two distance done you put it into the queue
05:16
and you have replaced the distance array as well now this is node three what you'll do will again update the distance to two let's quickly check for node 3 previously you have reached with a distance 1 which is sensible because if you directly traverse from 0 you'll reach at a distance 1 why do you want to
05:32
go via 1 by taking 1 plus 1 2 so this will discard it this will be discarded so thereby i just get one guy two comma two which has been put into the queue data structure as well as i've initialized the distance array so what i
05:47
can say now is the task for the node one is done i'll get the next node which is node three so let's get the next node node three and i'll take a distance of one now from three where can i go i can go to a node zero and i can go to a node
06:03
four as well so over here if i get a node zero and that's a distance one so from three to node zero that will be another plus one this will be another plus one so this distance will be two and this distance will be two let's quickly analyze does node zero has
06:18
already been yes it has already been reached at resistance zero discarded has note four been reached no infinity so what i'll do is i'll take it to the distance two and i'll say four comma two to be inserted into the queue data structure node three is done now
06:33
perfect i'll get the next guy two comma two so node two with a distance two perfect so next where can node two go let's analyze one and six so it can go to node one and node
06:49
six so if it decides to go to node one what will be the distance plus one of the previous previous was two so distance three plus one of the previous or distance three let's analyze node one node one has already been reached via distance one so why do you wanna take it so this will be discarded node six has
07:06
never been reached so you take the distance three yes you take the distance three and put it into your distance array so six comma three will be inserted into your distance and you'll update the distance array as well done let's see the next guy four comma two so four
07:22
comma distance of two let's see what the notes are for it's three comma five so let's quickly take node of 3 and node of 5 and let's figure out what is the minimum distance so if i figure out the
07:37
distance will be plus 1 to it which will make a distance 3 this will be also plus 1 which will again make the distance to be 3 so let's analyze node 3. node 3 has already been reached with a distance 1 so i'll discard it what about node 5 node 5 is infinity node 5 is infinity so
07:54
this is the first time i'm reaching at a distance of three so five comma three will be inserted into the queue data structure so what i can do is i'll quickly now erase this off perfect let's get the next guy six so node six at a distance of
08:10
three perfect so at node six where can i reach you can reach a lot of guys two five seven eight so what i'll do is i'll try to go to node two node five node seven a lot of guys are there please try out everyone
08:26
note 8 let's see for node 2 if i try to take the distance it'll be 4 will i consider it no we have already reached it so this will be discarded so let's discard it only the distance 4 again have i reached five yes at a three distance this is four so discarded
08:43
what was this distance four for seven it's infinity so you'll say four and you'll take seven comma four and you'll put it so this is taken what about eight eight will have a distance four because i'll do a plus one so eight comma four will also be taken into consideration so what i've done is
08:58
i've updated the distance array and i put it into the queue data structure as well so i'll erase it perfect let's get the next guy five comma three so node is 5 the distance is 3 so what will you do you'll try to get the adjacent nodes of 5 again that's 4
09:14
and 6 so let's write 4 and let's write 6 as well whatever the distance it's 3 so plus one plus one more then it the distance will be now four over here the distance will be four again so what i can say is for node four
09:30
the distance was previously two so i'll discard it and over here for node six the distance was three i'll discard it as well so let's discard both of them so we did not get any new shorter distance so i'll just erase it
09:46
what is the next thing that i'll do i'll take seven comma four so from node seven where can you go let's quickly have a check six and eight so let's try to go to node six and node eight perfect what is the distance can i say it will be a plus one so distance will
10:02
be five can i say it will be plus one over here so distance will be five so as of now node six at a distance five we already reached it at a distance three no need to take it the discarded what about this node eight has already been reached with four so discard it so again i have made sure that this
10:19
does not gives me any shorter ones and last one is node 8 with our distance 4 so what the adjacent of 8 6 so let's try for 6. you'll get the distance as five because you do a plus one and the other node is
10:35
seven so you'll get the distance as five again and seven you can see is already been reached with four so no new nodes with shorter distance are found so ultimately you'll see that q becomes empty ultimately you'll see that q becomes empty so all the nodes that were
10:50
reachable has been updated with their shortest distance and if any node was unreachable it would have stored the value infinity if any node was unreachable it would have stored the value infinity apart from that you can see the shorter
11:07
distance been updated in the distance array that is how easily you can solve this particular problem by following a simple bfs algorithm and instead of a visited we keep a distance array which tells me what is the shortest distance that has been previously visited to this
11:23
particular guy so i hope you've understood the entire explanation it's time to code it up so as usual i'll be coding the c plus plus code on the right and you can figure out the exact similar java code on the left so what are we given we are given uh the edges the nm and the source node so at
11:42
first we need to create the graph so let's quickly uh create the graph so vector of adjacency list and then we can go across all the edges that's how you do it and if this is the vector i can say adjacency of i t of 0
11:58
because that's the edge and i can say id of 1 is when you push it remember it's an uh undirected graph so it will have both side edges so make sure you create the graph like this so once the
12:14
graph is created what did i tell you i need to create something as a distance array right so kindly go across and say distance of n and everything needs to be initialized with an infinite value so go across and initialize that with an infinite value so distance of i will be really i'll
12:29
keep the infinite as 189 and then i know the source whatever is the source given because source to source is always zero so that is what i'll give and right after that what i'll do is i'll say q okay and i'll start the queue with the source itself so q dot push i'll keep the
12:46
source now what do i need to do i need to travel in the queue till it is not empty because i need to perform a standard dfs sorry standard bfs rather this is what i'll do after this i'll say ind node equal to q dot front once i've said that i can do q dot pop and after
13:02
that i have to travel to all its adjacent nodes it's quite simple if you do this this in this way you can travel through all the adjacent nodes but now what is id id is an adjacent node to the node right so in order to reach from node so
13:17
till node it's distance of node from there one more because every edge has an unit distance so one more if that's less than to what i require previously to reach the node i t so what i'll do is i'll go distance of i t one plus distance of
13:33
node that is what i'll do and i'll ask the queue can you please store it because it's a new node so can you please go and store it once i've done that i'll go back to the question and say i'll read the question and it says that if you find the shortest path and return minus 1 if it is not possible
13:50
so i need to return a list really i can uh keep something like an answer of n size and everything initially initialized to minus 1 and i can go across all the notes which is quite simple and right after that what i'll say is hey listen if uh the distance of i is
14:07
not equal to 189 because initially we stored 189 assuming that none of them are reachable if it is not then we know it's reachable thereby it has updated its distance so else answer of i is equal to distance of i so for all the nodes which will contain 189 it will
14:25
stay as -1 otherwise we'll update the answer and right at the end of the day what i can say is can i please return this list once you've done this what you can do is compile and run this so you'll see that all the test cases are running absolutely fine so a quick uh thing
14:40
why do we follow the queue method and why not the standard algorithms that we are going to learn in the future so if you clearly see that since it is increasing by plus one as you saw in the explanation the queue will always store like the first it will store source which will take distance zero then the
14:57
next guys who will come at that will always come at distance one because the edge weight is increasing by one then the distance two will come then the distance three will come so if you look at the queue it's already sorted first the source at zero then distance one then distance two distance three it's
15:12
already in the sorted order so do you need so you don't need something like a sorted data structure to sort them in distance that is why q does work in a proper way and the time complexity taken will be similar to what we usually take in a bfs algorithm so you can call this
15:29
as a bfs algorithm where we have applied a slide of greedy algorithm to make sure that we always compress the distance and this is how you can easily store it and if i talk about the overall space we are creating the graph so that's going
15:44
to take some space here using the distance by using the queue so these three are taking some space and about the time complexity it is more uh similar to what the bfs generally takes which is v plus 2 e so that is what the time complexity will be if you omit these uh things in overall you can say v
16:01
plus 2 e so guys i hope i was able to explain you this particular problem just in case i was please please please make sure you like this video and if you're new to our channel please do consider subscribing to us that is my only request and if you haven't checked out our dp series and the hdc the links are in the description
16:17
please please do make sure you check it out with this let's wrap up this video and meet some mother tell them but why take it whenever your heart is [Music]