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.
@@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 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!
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 :)
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]'.
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.
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?
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
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.
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
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
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. :)
I didn't get it how path recreation in your code sample helps to find shortest path, looks like you just traverse it back as it was stored but there could be multiple ways to reach the same cell on the way, especially in case with diagonals and its not evident in your code how you address such issue. I am not seeing it in area about writing into the prev table and not at area where the previous node is read from it. So basically it should be dijkstra.
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.
your pseudo code looks a bit similar to what is on wiki, except on the wiki page they stop as soon as they reach the goal. you are making a tree from the entire graph which seems not efficient. just stop when you get to the end node.
Can you explain why it's not O(nlogn + m)? is it because each time you add or remove a node from a queue it's logx time (rather than logn)? so you're effectively doing n number of logx operations which round down to n number of primitive operations? ... like log(|Q|) < log(N) < N
@@WilliamFiset-videos Right! sorry I was somehow only thinking of priority queues (binomial and binary heaps) forgot about the properties of a simple linear queue! Thanks a bunch William!!
Just a question, why not make prev a hash table? and then we can even get rid of visited. If the presence of a node is in the prev table, then it's already been visited.
@@WilliamFiset-videos Cant we do this. Create a Hashmap. then put something like map.put(s, new LinkedList) and then track all visited in an Array. In this case we will be simply traversing. A bit of generic approach.
