🚀 Add to Chrome – It’s Free - YouTube Summarizer
Category: Algorithm Tutorial
00:00
hey everyone welcome back to the channel i hope you guys are doing extremely well today we will be solving the problem shortest path in directed acyclic graph given a directed acyclic graph find the shortest path from the source they've
00:15
clearly stated that the source will always be zero to all the vertex okay so basically what does the problem state uh you're given a dag now what is a dag if you remember it's a directed graph
00:30
with no cycles if i combine this then you call it as a directed acyclic graph that is the definition of it so over here you're given a graph now do you see a shuttle change from the graphs that we were doing till now yes you do so if you see
00:47
0 and 1 there's an edge but we have added edge weights to it we are saying the edge weight is 2 that means to go from zero to one it will take you two to go from one to two it will take you three so in short if i ask
01:04
you to go from zero to one what is the shortest path it takes two are there any other paths in the graph the answer to that is no so i can say if i say node one the distance is two because that is what it will take for node zero the distance is zero why
01:21
zero on itself because the source node has been clearly stated as zero so zero to itself will be zero right if i ask you for z the second node it states three where's the second node here how many parts are there one is this which takes
01:38
five one is this which takes three so thereby the shortest path is three so the question is very straightforward and simple you're given a source and it will always be zero from zero to all other parts like all of the notes zero one two three
01:53
and so on till n minus one node you have to find me the shortest distance to travel shortest distance to it that is what the question states so you have learned topo sort tell now right so you'll be applying topo sort
02:09
but the algorithm will be slightly different this time okay i'll be uh combining topo sort with some relaxation of edges to solve this so i like the steps and the process that i'll follow is first i'll tell you the algorithm
02:25
then we'll go and code it so that after this process you have a very strong hold of what we are doing once you understand this i will tell you the intuition okay you might think why not intuition at the start because if i tell you the
02:40
intuition you might understand but in a very blunt manner you'll understand you won't understand in depth once you have the algorithm and the code in the brain and then i tell the intuition you'll be able to connect it and you'll be much like it will be easier for you to absorb
02:55
it okay so this is the dag and this is the corresponding adjacency list this time let's carefully see the six has an adjacency node of four six has an adjacency of node of four with a weight of two so instead of
03:11
storing an integer previously it was like six as an adjacency node of four and five four and five this is what we were storing right this time we will store pairs four comma two five comma three because this is five will store pairs this time this time it
03:28
will be list of pairs either you are in c plus plus it will be vector of pairs what you will store if you are doing a java it will be a list of pairs that you will store in this particular thing remember the third lecture where i told
03:43
you how to store graphs if they have edge weights you always declare it as pairs and you store pairs where the first guy will be the adjacent node the second guy will be the weight of that edge remember so that is what i have done over here
03:58
so the question stated the source will always be zero but we will try to solve this problem for any given source so source can be anything so thereby what i'll do is i'll say for this graph assume the source to be six for this graph assume the source to be six
04:15
because i don't want you to be sticking with zero because that will not help you out so we can have any source because the interviewer might give you the question as stating as any source so any source okay so what is the step one so the step one of the algorithm is very
04:30
simple do a two possible do a two possible on the graph yes do a two pose sort on the graph now how many ways do you know to do a tuple sort there are two ways one is the dfs way one is the bf space to whichever you wish to i just want the topo sort for
04:47
this particular dac which is the directed acyclic graph so let's quickly do the topo sort for this dag so i'll be using the dfs method to find the toposort so you know the dfs method is very simple we always take a stacked data structure which stores the
05:03
toposort whenever we complete the dfs or a given node we put it into the stack we take a visited node that is what we take and we always run something like this for i equal to 0 and we go until 6 and we say if not visited of i
05:20
then please call the dfs for i if you remember this is always done for the components right so the first value of i that's zero so we'll go and call the dfs for zero the dfs of zero is called whenever the dfs of zero is called
05:35
please make sure it is marked as visited now who are zeros adjacent nodes it appears that zero's adjacent node is one so go and call the dfs for one perfect so again mark it as visited once adjacent node appears to be three so go
05:52
and call for three so i called it for three or four three appears that there is no one for three mark three has visited and it appears that for three there is no one so what i can say is for three the dfs call is over and whenever the
06:07
dfs call is over in tuperson if you remember we just took that three and put it into the stack go back one do we have any further adjusted nodes no put it into the stack go back zero do we have any further adjacent nodes no put it into the stack and go back so what i
06:23
can say is this particular dfs call is done let's increase the value of i one it's already visited two not visited call it for two mark it as visited what two do we have any edges and notes yes what is it three but it's already
06:40
visited no for the dfs calls so two is also done go back so once you go back this is done increase the value of i because this will be three will we do our dfs call for three no it's already visited increase the value four so will we do it for four yes we'll do it for
06:55
four mark four as visited after that look at four it has zero which is visited you see zero is visited it is and it has three uh two which is also visited zero and two both are visited separately no for the dfs calls so it
07:10
will go back and reverse put it into the stack and go back next it's 5 for 5 mark it is visited and 5 has adjacent node as 4 which is already visited so no further defense calls please make sure put 5 into the
07:26
adjacent nodes and go back next into the stack rather it'll be six similarly it will happen for six mark it as visited and you'll find that for six we have four and five as the adjacent node four and five both are visited so
07:41
no further dfs calls put it into the stack and go back so apparently once this for loop has been completed all the defense calls have been completed this stack will store the topo sort now if i quickly erase this off let's
07:56
quickly raise this off so the step one i can say has been completed and the toposoda is very simple it is 6 5 4 2 0 1 3 and if you carefully see there is an edge between 0 to 1 0 appears before 1 there there's an edge between two two
08:12
three the two appears before three so this is indeed a valid topo sort i can easily say that now what is step two step two is very very simple you take out all the notes from the stack one by one take the notes out of the stack one by one notes out of stack
08:31
and relax the edges you'll hear this term a lot going forward and relax the edges okay this is the step two so in order to relax the edges we need to declare a distance array and that should be marked with infinity let's do it
08:46
the distance error has been declared and what you'll do initially is just make sure everything is marked as infinity now let's start relaxation of the edges but before that please make sure whatever is your source node just go to that source node and make it zero just
09:01
make sure that you go to that source node and see that hey i know one thing if you start from six and if you end at six the distance that you will take will always be zero so make sure you do that okay next whatever is on the stack stop this is stack stop stack is always
09:17
last in first stop so the last inverse six this is stack stop so make sure you take it out the node equal to 6 has been taken out now whenever you are at 6 you know the distance to 6 is 0 how did you figure this out because that is what it was stored over
09:34
here right now figure out the adjacent nodes of six that is the nodes of six is four and five the adjacent node of six is four and five so try to go there so you will be like okay i'll try to go to node
09:49
5 i'll also try to go to node 4 okay these are the two nodes that i'll try to go to these are the two nodes that i'll try to go to now have a careful observation have a very careful observation on this graph in order to go from six to five
10:06
which is this what is the edge weight that is required three do you see three so you say if i go i'll require a three so can i say if in order to reach 6 i required a distance of 0
10:22
from 6 to 5 i require a distance of plus 3. can i say the overall distance will be 3 because from 6 to 6 it was 0 and from 6 to 5 it is 3 so the overall distance will be 3 and you see to node 5
10:40
it was infinity right and if you see we are reaching a distance 3 which is better three obviously so you go and update this to three you go and update this to three don't do anything else just go and update similarly see over here to node four what will you require two
10:57
so please do a plus two the distance will be two similarly go to node four and see you will require a distance of two you will require a distance of two done once you have checked out all the nodes completed next get the next node
11:13
out which is five and let's see what is the distance taken to five that states me that the distance has been taken as three it's clearly states as three the distance is three what does it mean what was whatever was the source node in order to get to node 5 i
11:29
required a distance of 3 that is the meaning of it so for node 5 look at the uh nodes so the nearby node is poor the nearby node is 4 how much will it take if it goes from four five to four one plus one is what it will take let's uh
11:46
let's take the distance so previously it took three in order to reach from six to five that's taking plus one the total distance will be four t plus one is four and if you carefully see in order to reach node four i already have a better option i already have a better option of
12:02
two so will i take this four no why very simple because from six to five and five to four it will be four and from six to four it will just be two which we already have taken so nothing to be done omit this off next take the next guy
12:18
note four at the moment you take note four what happens you again check for the adjacent nodes that's zero and two so one is node zero and the other one is node two this takes a distance of plus three
12:34
this takes a distance of plus one very simple to figure out you have already stored it so plus three and plus one previously how much distance node four took two again very simple to get from here so six two four took a two plus three so till node zero what will be the distance
12:51
it will be nothing but very simple 5 until here it will be nothing but 3 why 2 plus 3 will be 5 2 plus 1 will be 3 so node 0 states it's infinity so you update it to distance 5
13:08
and node 2 says it's infinity so you update it to distance 3 done once you've done this omit this as well simple next take the next node which is two so node two what is the distance taken
13:24
three from the distance array so from six to two you know the distance is three you know the distance is three from six to two you know the distance is three and that's very obvious because it took this path it took this path right so from node to where can you go let's quickly check it
13:40
out from node two you can go to three so let's write it you can go to three and if i go to 3 i will require how much 3 i'll require nothing but 3 so i'll just add a 3 and that will give me nothing
13:58
but distance of 6 so till node 3 i get a better option than infinity so i take it next erase it it's really take the next one which is zero so node is zero the distance taken is five from zero you
14:13
can go to node one and the distance will be plus two of it so the distance will be seven what you can do is you can say one to be seven very obvious because if this is taking five and this takes another two so five plus 2 will be 7 which is
14:30
better than infinity so done omit this let's say the next guy who is 1 so from node 1 what is the distance 7 you see node 1 has distance 7 where can one go one can go to node three how
14:46
did you get this from here what is the distance plus one so what will be the distance if i go to node three eight will i take this no why because we already have a six to omit this we will not take it similarly we'll get the next guy which
15:01
is three so node is three so from three where can you go you can go nowhere there's nothing to be done omit this this is the step two so once you have done the step two you can see that the distance array actually stores all the shortest distance from
15:18
the source six and the topo sort is empty and we have figured out how this is our answer yes this is what our answer is so i hope you've understood the algorithm it's very straightforward and simple figure out the tuple sort
15:35
once you've done that take one one node out and just keep on updating the distance array keep on updating the distance every time once you're done with this this is your particular answer what's the intuition after the code i'll tell you so i hope you've understood the entire
15:50
algorithm now it's time to code it up so i'll be coding the c plus plus solution on the right and you can figure out the exact similar java code on the left so as you can see we are given the number of nodes the number of edges and all the edges data have been given over here the edges data is like
16:06
u and v and the weight so the first step is definitely to create a graph so let's quickly create the graph which will be something like vector of pair we need to store pairs this time so adjacency of n okay next we go across and say i and d i equal to zero i lesser than n i plus
16:22
plus this is something which you will do how's the next thing that i'll do is the adjacency of u by the way just uh to make your understanding better edges of i zero because every index has a vector and the vector resembles three guys that is the meaning
16:38
of this so u is this v is edges of i of one and w d is on the second index simple as that next i say adjacency of you can you please store the adjacent guy which is v and
16:55
the weight is wt as a pair stored next you always find the toefl so that's the first thing so what do i need i need a visitor direct i need a stack and do i need anything else no so let's quickly create the visited
17:11
array so i create a visited array something like this now which is capital equal to zero perfect uh i need a stack so let's quickly create a stack as well perfect next i need to uh figure out uh for all components so let's go for all
17:26
components and we say if not visited of i we go across and say okay listen go for the tube so and in those two sort what do we need we need the node we need the adjacency we need to visit it and we need the stack so this is what i'll do i'll get my tuple sort
17:43
so now quickly write the tuple sort and that's for dfs you can always write whatever you wish you can do the bfs as well void dfs id node and i'll say vector of pair of int i int int int adjacent this is how the
18:00
graph will be perfect next i need the visited so let's see the visitor and this is the stack which is int and please pass it using reference so that's what i will do what's the first step of dfs you say by the way this will not be dfs this will
18:15
be two sort that's what we are naming it visited of node will be one and while going back just make sure you push on the node next i traverse all the adjacent nodes which is adjacency of node now i know v is
18:31
the node is right at the first because we are storing pairs so i see if not visited of b please go and call the two post it's very simple because we will be calling the topo sort for v adjacency visited and stack
18:48
done so this is how i'll call the topo sort so i can say once i've done this the stack is ready and it has all the tuple sort elements next step two do the distance thing do the distance thing and what do i need uh what do i need for doing the distance
19:04
thing i need a vector which stores all the distance perfect please make sure everything is initially marked as infinity so i this and you can go on like i less than n i plus plus and you can go as distance of i
19:20
equal to infinity you can call it as into max super simple next you know you have a source node and that's always zero if the question does not mentions your source node and it gives you you have to write distance of src equal to zero next you start from a wire and you say stack not empty that's the first
19:37
thing you'll do what what will you do over here you'll say okay let's get the note which is stack the top and let's do a stack dot perfect next you need all the adjective notes so please go across all the adjacent notes and you know over here idv id dot first
19:54
stores the adjacent nodes and id dot second stores the wait and i need to relax it so distance of node is what it takes to reach the node and from u to v it takes sweet and if it is lesser than the previous
20:10
uh way of reaching v it can be infinite it can be anything if node plus v it is lesser than the previous way of reaching it i do not do anything i just go across and update it to the new node this is what i'll do i'll just update it to new node once i've done this i'll
20:26
return the distance so this is how simple it is and after this i'll go across and run this and see if it is fine it gives me a compilation error because i think we uh my bad it will be pushed back so let's quickly run this so i've done a slight typo over here it will be in m
20:43
because number of edges i'll quickly compile and see if it is giving us the correct answer in compilation we see that it is giving us the correct answer will we submit no let's wait let's uh read a couple of uh statements so it says find the shortest path but does it mentions about what if
21:00
it do not reach so it doesn't mentions about it i'll ask the problem setter to add it up but as of now there's a trick i'll go ahead and i say okay they're expecting if it is 189 to see out infinity not reachable but they're expecting one e9 instead of into max so
21:17
i'll just assign 199 because what they're expecting is if it's not reachable it should be 189 so i just did a slight hack i just checked in but i'll ask the problem setter to update the problem statement don't worry about that i'll now quickly uh run this off and see if it is running
21:33
fine okay it is so all of these test cases to pass so we have understood the algorithm we've understood the code now let's discuss the time complexity then we will go across to the intuition what are the time complexity or topo sort plane dfs whatever time the default
21:49
takes what about this the number of nodes is what the stack will always give you that's for sure the number of nodes is what the stack will give you which is n into all the neighbors into all the news so if i ask you in total this for loop will run for
22:05
how many times let's go back so can i say in the uh ipad runs for first round zero will run for once twice price four times five times six times seven times eight times can i say the internal fall for loop for
22:22
the adjacent nodes will run for one two three four five six seven eight times which is nothing but one two three four five six seven eight which is nothing but the m edges and i say overall it will run for images so n plus
22:38
m is what the second loop will run this is a plane dfs this is plane dfs n plus e the number of edges which is m but this is very obvious right because the stack will give you n and in total the adjacent nodes is nothing but
22:55
the number of edges only so we have understood the uh time complexity as well now it's the main thing about okay so you've understood everything now i must be thinking about the intuition why why not some standard algorithm like in
23:11
the next uh half of the lecture like in the sorry in the next half of the series we'll learn algorithms like dijkstra and a lot more which helps us to find the shortest path will those algorithms work those algorithms will definitely work but why did we do a tuple sort let's understand so what was the tuple
23:29
set for this if i write it it was 6 5 4 2 0 one three something i know for sure is there is no one before six there's no one before six so something i know for sure is the initial guy is six so i took the initial
23:45
guy to be six and six took me to four and five so apparently once i started from six which was the topo sort then i could go to the next guys and that will always be in my two post only this topo sort starts with the first guy who has no one
24:03
into it and then takes to the next guys who he was into who he was into just so takes it to five because it was just two five and five says i'll take you to four all right so what tupusa did was it stated as the first cat i don't have
24:19
anything i'll start off from myself and since i was the source node i'll assign myself to be zero i'll go to five i'll figure out the answer for five then i'll go to four figure out the answer for four then i'll go to zero and to figure out the answer for them then i'll go to three then i'll go to one and
24:35
i'll figure out so what i did was i moved sequentially the nodes which are reachable first i moved them then this then this then this then this then this then this i moved according to reachability moved according to reachability
24:52
so what happened was i minimized the number of steps to be go of n plus m which is much much better than any standard algorithm because nexo takes more than this the only reason it works is because
25:07
we are making sure there was no one before six and we computed for six then we did for five so when we are doing for four we know all the previous guys have been computed and i have i can only reach four via six or five because it is a directed graph
25:24
two zero one three cannot make me reach for the guys who can make me reach 4 are 6 and 5 and they have that their answers come computed so i'll compute r4 now for 2 these 3 guys can make me reach 2. so these answers are computed so i
25:40
started with a very small and then i expanded it to 2 then i expanded it to 3 and so on that is how we will do it so in short the intuition is very straightforward if i'm reaching a node i know all the previous nodes have their answers right so that was the simple intuition
25:56
we still have a problem i'll leave a stack overflow link on the description you can check it out or the answer is given over there you can read it again and again but i think it is more or less clear to you know so i hope you understood the algorithm the code and the intuition so just in case you did please please please make sure you like
26:12
this video and if you're new to our channel hit that subscribe button right away please do consider subscribing to us if you haven't checked out our dp series and the hd sheet the links will be in the description and here with this i'll be wrapping up this video let's meet in some other video till then bye take care whenever your heart is broken
26:31
[Music]