Wow this is such a basic concept I can't believe my teacher couldn't explain it. He just gave us actual code to start out with. Universities seriously need to stop hiring grad students as teachers.
Trying for 3 hours to do it myself, came here to see the solution. I forgot the prev array, and In fact even If I visited the whole graph and found the final node, didn't know how to reconstruct everything :D Thanks a lot
Wow, so many great tutors on the internet already, but you have explained it in a very digestible manner, thank you for your service, this helped me in getting my first dev job.
I love these ones that focus on the actual useful abstraction instead of trying to explain it concretely in mathematics. If I didn't understand the abstract, I wouldn't be studying computer science! Stop putting the cart before the horse!
Great video! Do you mind explaining how the for loop in the reconstructPath method works? Specifically, for(at = e; at != null; at = prev[at]) How is this being updated to continue thru the loop? Thanks again, William!
Yeah, the prev array at index i (i.e prev[i]) contains the index of the node used to get to node i. To reconstruct the path we work backwards from the end node 'e' until we reach the start node. The start node does not have a parent so that's why we have 'at != null' as the end condition. Each iteration of the loop you trace back one node, this is 'at = prev[at]'.
@@hungp9227 I haven't applied dumbass, retarded companies will want you to answer their stupid fucking algorithm questions and give you a job that has nothing to do with algorithms. That's why algorithms are shit
How do you know that you are following the shortest path when you reconstruct the path from e? What if there was more than one path to e? Wouldn't the last path to reach e be the one that is set in prev?
since e is put into the visited array, prev would not be overwritten. I also wondered why always the shortest path is found but since the algorithm is filling the search field from s to e, as soon as e is reached, it has to be the shortest path. all resulting paths are parallely searched on step further so the shortest path to e will always emerge.
@@silviogames So I interpret your explanation as that the FIRST path being found is the SHORTEST path. Is this correct? And this is achieved by the layering and queueing concept of BFS. The path found first is the path found at the lowest layer (closest to the source node).
@@An-wd9kk yeah. lets assume there exist 3 paths to the goal but the algorithm will always move one step at a time so the first that wins has to be the shortest. the others will either be same length or longer
Hi, i have a doubt. Since the values are marked from 0-12, graph.get(node) works perfectly considering the node value is the index value. What if the values aren't like this? Instead of graph.get(node), do we run a for loop to find? Please help & Nice video btw. :)
6 years late but I do have a question. When you first start the queue why do you choose 9, 7, 11 ? could you also choose 7, 9, 11 or 11, 7, 9 etc.? or is there some reason you chose 9, 7, 11 ?
Hey, important little thing: krep some padding at the bottom becos of the sub. I watch videos with subs, and i could not see the bottom of the graph. Aaaand, cool video :)
Awesome videos william. can you maybe discuss this problem. there are 'n' nodes and 'm' edges in a graph. each node may or may not contain certain number of a item. all nodes have same item but different number of that item. we have to go from source to destination in minimum time collecting 'k' number of this item. each edge is weighted,weights may or may not be same. there are no self loops. edges are bidirectional.
Excellent video! Just a question. The prev array will contain ALL the visited nodes. I can not see how the reconstruct method will return the fastest path. Can anyone explain please?
True, the prev array contains all nodes, but we're only reconstructing the shortest path between s and e. When we reconstruct the path we begin at e and add the node we used to get to e when we did the BFS (this is prev [e]), then we do the same thing and add prev[prev[e]] to shortest path and so on until we reach s. This will not visit all nodes -- except in the worst case (e.g your graph is a a straight line)
@@WilliamFiset-videos Hi, this is a little bit late, but I am having trouble understanding how we know which node was the one that led to e, when "prev" seems to hold all the nodes?
@@gruuvy8067 The BFS search creates what is called a "BFS tree". The root is the starting node s, and the edges in the tree represent that from a node we visited another node. "prev" maps each node to its parent in the BFS tree. By starting at a node e and following the sequence of parents in the BFS tree, we arrive at the start node s in the shortest number of steps.
@@gruuvy8067 In the prev array, you start with searching for the value of the e'th (e is the ending node) index, this value is the node preceding e in the shortest path from s to e. Use that value as the next index to search for in the prev array and so on till you reach the start node s.
@@roberthoffenheim7861 why not come to a grinding halt when you hit the end node in function 'solve' - instead of doing all nodes in the try, which seems inefficient
The visited queue would contain ALL of the neighbors that were visited, right? How would simply reversing the visited queue give you the shortest path? There would be visited neighbors in the queue that were not along the shortest path. How do you prune out those suboptimal neighbors?
Am I missing something or did this not actually talk about how to get the shortest path from BFS? Or did I just lose track? I followed the initial visualization (very helpful) but that didn't show the shortest path right?
If you look in reconstructPath towards the end around @7:00 and observe that first for loop closely, it starts at the end node, records it and goes to its parent in prev, then it calls that parents prev until null and the only one that should have null listed in prev is the original node s. So by only jumping from child to parent, from end to start this IS the shortest path once we reverse it.
@@euclid9492 I don't understand your "only jumping from child to parent" argument. It only implies that the path is non-cyclic or straightforward. It does not imply shortest path. Both path a->b->c and a->d->f->c satisfy that we jump from parent to child, but the former is clearly the shorter path.
@@An-wd9kk That is correct if we are only looking at the reconstruct path function. What we need to remember though, is how we mapped the child to parent INITIALLY in the phase before that. We check a nodes immediate neighbors first so there is no way to get shorter than that. Once a node is visited, it’s parent is recorded and will not be overwritten. Because of this, sure a longer path could exist, but because of the way we stepped out checking immediate neighbors first, the path that we get will be guaranteed to be the shortest path. I had to follow this out on a whiteboard before it clicked, if you have time, I’d recommend doing the same! Hope that clears it up a bit.
@@euclid9492 Everything is probably right in the video but i don't understand what happens (or rather how the right thing would happen) when a node has multiple parent nodes, as only one parent node is is saved in the prev list? And after the first parent node is saved, the "kid" node won't be visited anymore to save any other parent nodes.
When adding the root node's neighbours to the queue, why does it not go in an order (e.g. smallest to largest or vice versa). Is this algorithm just trying to visit every node in the graph as quick as it can?
The algorithm will try to explore the entire graph in a breadth first manner. The order in which you add the roots neighbors to the queue doesn't matter for exploration purposes
I think this one could use a little bit better explanation at the start. DFS is pretty obvious and intuitive but this one left me kind of wondering exactly how a BFS gets you the shortest path.
I completely agree. It took me a while to realize that when constructing the prev array we're basically calculating the shortest path to any given node in the graph from the start one.
@@jomalomal Everything is probably right in the video but i don't understand what happens (or rather how the right thing would happen) when a node has multiple parent nodes, as only one parent node is is saved in the prev list? And after the first parent node is saved, the "kid" node won't be visited anymore to save any other parent nodes.
The queue will be ordered by layer, but the nodes of any particular layer can appear in any order, so if you start at 0, in the next layer it's valid to add 7, 11 and then 9
![KRK - ชนิสรา Ft.WanMai , N/A [Official MV] Prod. By Sakarin](http://i.ytimg.com/vi/C-WMwwYobcU/mqdefault.jpg)
the best explanation I 've seen fo far. Simple, clear, and focus without redundant words. Saving a lot of time. Love it and subscribed
Agreed
@Louis Jesse dude you chose the wrong type of people to dump your bs on. computer scientists dgaf about your animal relations.
You turned 2 hours of confusing lectures into a simple 7 minute video. Thank you!
Wow this is such a basic concept I can't believe my teacher couldn't explain it. He just gave us actual code to start out with. Universities seriously need to stop hiring grad students as teachers.
You're one of the few explaining it with an end node and path reconstruct. Thank you!
Thank you so much!! As a really confused CS student who just started algorithms course this helped me a lot!
how is it going ?
Trying for 3 hours to do it myself, came here to see the solution. I forgot the prev array, and In fact even If I visited the whole graph and found the final node, didn't know how to reconstruct everything :D Thanks a lot
Your animation just clicked it for me. Awesome :)
I appreciate the effort you put into making these tutorials man. You are the best.
You have saved my academic.
Thanks!
The best video about BFS I've watched! Thanks I already understand it! :D
Wow this is by far the most understandable explanation of this concept that I've seen. Thank you!
Good explanation. That queue drawing finally helped me get it.
Wow, so many great tutors on the internet already, but you have explained it in a very digestible manner, thank you for your service, this helped me in getting my first dev job.
Best explanation ever, hope to see more videos like this from you William! Keep up the good work
Best Explanation and Representation for BFS topic on TH-cam...
Currently implementing this "in the wild". Good to see that the "right" way to do it is pretty much what I figured out
This is the best explanation I've seen so far. Thank you!
This Channel is really Helpful and informative and explained very well
this video is a miracle of learning
Thanks for your time sir ...the best and simple explanation .
Crystal clear explanation. Many implementation details well covered!
The first half was totally understandable. and the other half... also understandable
Holy crap the queue example is perfect
this is an awesome explanation. Thank you very much.
This was extremely useful. Thanks!
Keep working this way!
I love these ones that focus on the actual useful abstraction instead of trying to explain it concretely in mathematics. If I didn't understand the abstract, I wouldn't be studying computer science! Stop putting the cart before the horse!
Great video!
Do you mind explaining how the for loop in the reconstructPath method works?
Specifically,
for(at = e; at != null; at = prev[at])
How is this being updated to continue thru the loop?
Thanks again, William!
Yeah, the prev array at index i (i.e prev[i]) contains the index of the node used to get to node i. To reconstruct the path we work backwards from the end node 'e' until we reach the start node. The start node does not have a parent so that's why we have 'at != null' as the end condition. Each iteration of the loop you trace back one node, this is 'at = prev[at]'.
@@WilliamFiset-videos Thanks William! Really appreciate the reply! Keep up the great work!!
@@WilliamFiset-videos thanks I also got stuck there
@@bl4ck21 In the first iteration, at =e. In the second iteration, at = prev[at]. Each time, at is incrementally progressed to prev[at].
That's a fantastic explanation. re watching BFS for my job interview. thanks mate.
why the fuck do you need to know that shit for a job interview. Is the interviewer gonna give you a algorithm exam.
@@CloroxBleach-hi6jd Plenty of job interviews go over your data structure and algorithms knowledge...
@@ade1819 That's bullshit, if you have the degree than you've taken the class. Fuck algorithms anyway, coding is fun but algorithms are confusing shit
@@CloroxBleach-hi6jd this is why companies don't hire you
@@hungp9227 I haven't applied dumbass, retarded companies will want you to answer their stupid fucking algorithm questions and give you a job that has nothing to do with algorithms. That's why algorithms are shit
I could listen to your voice all day
Thanks for the easy and understandable explanation
Very good explanation and it is nice that you added pseudocode !!!!
You are a legend! Best explanation ever!
I am late to the Party but i want to say: Great Tutorial! Exactly what i needed!
Thank you very much William. You are the best!
hi thanks for the very clear explaination, but I cannot find the code where we are trying to find the Min or max path from S to E
Great video! Thaaanks for the clear explanation.
Should not the reconstructPath function definition have ( if at == s { break; } ) in the for loop?
Thank you, this was very helpful!
Thank you so much, it helped a lot! Great video and explanation! (Greetings from Brazil!)
Best explanation possible. Thanks a lot!
Thank you bhai! I am grateful for your teachings
Your videos are the best on graph theory!
thanks man, amazing video. so straightforward and useful!
Best explanation
Thank you - this was easy to understand.
Why can't everyone just explain it like this 😂 Fully understood within 3 minutes
thanks for the amazing explanation!
Quality vids.. Subscribed. Thanks for your time and effort!
Great videos. Thank you so much.
Very clear, thank you so much!
brilliant video thanks
thank you so much !! 😄 ... awesome video 👍
Awesome video - thank you!
best explanation!!!!!! may god bless you
Just keep it up. Nice videos
Cant thank enough for this !!!
Thanks! You're godsend!
beautiful explanation :)
One of the best!
Thank you sir🙏
When adding to the queue, does it matter if we did 3,6 instead of 6,3?
Best of the best! thank you
How do you know that you are following the shortest path when you reconstruct the path from e? What if there was more than one path to e? Wouldn't the last path to reach e be the one that is set in prev?
since e is put into the visited array, prev would not be overwritten. I also wondered why always the shortest path is found but since the algorithm is filling the search field from s to e, as soon as e is reached, it has to be the shortest path. all resulting paths are parallely searched on step further so the shortest path to e will always emerge.
@@silviogames So I interpret your explanation as that the FIRST path being found is the SHORTEST path. Is this correct? And this is achieved by the layering and queueing concept of BFS. The path found first is the path found at the lowest layer (closest to the source node).
@@An-wd9kk yeah. lets assume there exist 3 paths to the goal but the algorithm will always move one step at a time so the first that wins has to be the shortest. the others will either be same length or longer
@@silviogames yes thank you for your answer.
@@silviogames I was trying to understand since two days and you exactly saved me. Thanks for explanation.
Hi, i have a doubt. Since the values are marked from 0-12, graph.get(node) works perfectly considering the node value is the index value. What if the values aren't like this? Instead of graph.get(node), do we run a for loop to find? Please help & Nice video btw. :)
you can map the node value while constructing the the graph using adjacency list or adj matrix.
6 years late but I do have a question. When you first start the queue why do you choose 9, 7, 11 ? could you also choose 7, 9, 11 or 11, 7, 9 etc.? or is there some reason you chose 9, 7, 11 ?
Hello! Why don't you check neighbours for null here 5:42?
Awesome explanation easy to understand , animations are great to follow along.Liked 👍and subscribed
Hey, important little thing: krep some padding at the bottom becos of the sub. I watch videos with subs, and i could not see the bottom of the graph.
Aaaand, cool video :)
Awesome videos william.
can you maybe discuss this problem.
there are 'n' nodes and 'm' edges in a graph.
each node may or may not contain certain number of a item.
all nodes have same item but different number of that item.
we have to go from source to destination in minimum time collecting 'k' number of this item.
each edge is weighted,weights may or may not be same.
there are no self loops.
edges are bidirectional.
I'm not sure i'm going to cover that problem per se but can you provide a link to the problem?
Excellent video! Just a question. The prev array will contain ALL the visited nodes. I can not see how the reconstruct method will return the fastest path. Can anyone explain please?
True, the prev array contains all nodes, but we're only reconstructing the shortest path between s and e. When we reconstruct the path we begin at e and add the node we used to get to e when we did the BFS (this is prev [e]), then we do the same thing and add prev[prev[e]] to shortest path and so on until we reach s. This will not visit all nodes -- except in the worst case (e.g your graph is a a straight line)
@@WilliamFiset-videos Hi, this is a little bit late, but I am having trouble understanding how we know which node was the one that led to e, when "prev" seems to hold all the nodes?
@@gruuvy8067 The BFS search creates what is called a "BFS tree". The root is the starting node s, and the edges in the tree represent that from a node we visited another node. "prev" maps each node to its parent in the BFS tree. By starting at a node e and following the sequence of parents in the BFS tree, we arrive at the start node s in the shortest number of steps.
@@gruuvy8067 In the prev array, you start with searching for the value of the e'th (e is the ending node) index, this value is the node preceding e in the shortest path from s to e. Use that value as the next index to search for in the prev array and so on till you reach the start node s.
@@roberthoffenheim7861 why not come to a grinding halt when you hit the end node in function 'solve' - instead of doing all nodes in the try, which seems inefficient
The visited queue would contain ALL of the neighbors that were visited, right?
How would simply reversing the visited queue give you the shortest path? There would be visited neighbors in the queue that were not along the shortest path. How do you prune out those suboptimal neighbors?
It was nice uptill midway, You didn't show, via diagram, the reconstruct path method logic. What happens after 3:00 ?
Best explanation!
What if there are multiple shortest path for s to e? And I want to retrieve all of them.
someone i can understand thank god
Am I missing something or did this not actually talk about how to get the shortest path from BFS? Or did I just lose track? I followed the initial visualization (very helpful) but that didn't show the shortest path right?
If you look in reconstructPath towards the end around @7:00 and observe that first for loop closely, it starts at the end node, records it and goes to its parent in prev, then it calls that parents prev until null and the only one that should have null listed in prev is the original node s. So by only jumping from child to parent, from end to start this IS the shortest path once we reverse it.
@@euclid9492 I don't understand your "only jumping from child to parent" argument. It only implies that the path is non-cyclic or straightforward. It does not imply shortest path. Both path a->b->c and a->d->f->c satisfy that we jump from parent to child, but the former is clearly the shorter path.
@@An-wd9kk That is correct if we are only looking at the reconstruct path function. What we need to remember though, is how we mapped the child to parent INITIALLY in the phase before that. We check a nodes immediate neighbors first so there is no way to get shorter than that. Once a node is visited, it’s parent is recorded and will not be overwritten. Because of this, sure a longer path could exist, but because of the way we stepped out checking immediate neighbors first, the path that we get will be guaranteed to be the shortest path. I had to follow this out on a whiteboard before it clicked, if you have time, I’d recommend doing the same! Hope that clears it up a bit.
@@euclid9492 Thank you
@@euclid9492 Everything is probably right in the video but i don't understand what happens (or rather how the right thing would happen) when a node has multiple parent nodes, as only one parent node is is saved in the prev list? And after the first parent node is saved, the "kid" node won't be visited anymore to save any other parent nodes.
5:27 shouldn't you add the node you just dequeued to the visited list, so that it won't get added to the queue again in the following iterations?
We have marked it as visited before starting the while loop
explanation is ok code is complicated
Around 4:50 you mention "value at index i". Sorry, what is the index i? Just trying to understand
how are you using the .get function in list?
Animation for path memorizing/reconstruction would be highly appreciated
How do u create suuch presentation
what tool do you use to make these diagrams?
Thank you!
Can you please help me...which tool you used for making graphs....I have to make them for my project and your diagrams are very clear 😀
Keynote
@@WilliamFiset-videos thank you so much
we need an order, right ? it goes like we start from the smallest number to the biggest or backward, am i right ?
Why do we start at 9 after 0? would we not start at 7? how do we determine the order things are added to the queue
When adding the root node's neighbours to the queue, why does it not go in an order (e.g. smallest to largest or vice versa). Is this algorithm just trying to visit every node in the graph as quick as it can?
The algorithm will try to explore the entire graph in a breadth first manner. The order in which you add the roots neighbors to the queue doesn't matter for exploration purposes
@@WilliamFiset-videos right, thank you 👍
I think this one could use a little bit better explanation at the start. DFS is pretty obvious and intuitive but this one left me kind of wondering exactly how a BFS gets you the shortest path.
Do it with an example, it'll be much more clearer.
I completely agree. It took me a while to realize that when constructing the prev array we're basically calculating the shortest path to any given node in the graph from the start one.
@@jomalomal Everything is probably right in the video but i don't understand what happens (or rather how the right thing would happen) when a node has multiple parent nodes, as only one parent node is is saved in the prev list? And after the first parent node is saved, the "kid" node won't be visited anymore to save any other parent nodes.
very helpful!
How can we be sure that this is the shortest path?
Been a whole year 🤣 idek
thank you sir very helpful but if you talk about algorithm analysis more it would be better.
At 2:07, why is 9 visited first instead of 7?
Can this search algorithm be used on weighted graphs?
If not, what else can be used?
If there aren’t any negative weights you can use Djikstra’s algorithm. If there are negatie weights, you can use Bellman-Ford
you are a legend
Is there any order for the queue ? Can i add 7 then 11 then 9 for example ? thx
The queue will be ordered by layer, but the nodes of any particular layer can appear in any order, so if you start at 0, in the next layer it's valid to add 7, 11 and then 9
How do we implement this on a weighted graph?
Complexity O(V + E) for directed graph, right? For undirected O(V + 2E). Correct me if I am wrong)
Big O takes care of the constants :)
This is awesome