This video is designed for individuals with prior knowledge of BFS and DFS concepts. It serves as a review for those already familiar with these topics, providing an opportunity to reinforce existing understanding. If you are not acquainted with BFS and DFS, it is recommended to gain proficiency in these concepts before engaging with this content.
I think it should be if((distance[neighbor] < distance[node] + edge) || distance[neighbor] == -1) Say starting node =1, end node = 4. Now say 1->3 is 10unit and 3->4 is 100unit. Then using above BFS it will find neighbor of 1 which is 2, 3...then ones it gets to 3 it'll find neighbor 0, 4, 6 and will update distance[4] = 110 But say 3->0 is 10unit and 0 -> 5 10unit and 5 -> 4 is 10 unit. Then once we get to neighbor of 5 the shortest reach using above program will say ohh I already visited "4" (because distance[4] != -1 it's 110) and it will skip updating the distance where it could have been 40Units(1->3 , 3->0, 0->5, 5->4 all 10 units) instead of 110.
The class "Node" has a LinkedList of neighbors. These are the nodes connected to current node. She included the implementation on her video titled: "Algorithms: Graph Search, DFS and BFS." What she didn't cover is how to create the graphs so that you could test your implementation. For this, you need two methods: 1) One to add Node objects to the Node array (on the other video, she used a Linked List and called it something different) and 2) the implementation of addEdge(int, int). That implementation is actually quite simple: public void addEdge(int source, int destination) { Node s = getNode(source); // This can return null Node d = getNode(destination); // This can return null s.neigbors.add(d); d.neigbors.add(s); } you could avoid returning null by using the Null Object pattern and have the getNode method return a null Node Object rather than a null pointer. Then, you need to connect nodes that are not instances of Null Node class. But this is a topic for another time. Also, d.neigbors.add(s) should be done only if you want bidirectional routes from node to node. Perhaps it is better to do without this step and add the edges when you create the graph, i.e. graph.addEdge(1, 2) and graph.addEdge(2, 1) . This way, you could make certain paths unidirectional and other bidirectional if needed.
was wondering if you could help me with a Maze program in java im working on, I'm trying to use a BFS to find the shortestPath and could really use your help :)
Since the graph is not weighted and bfs traverses all the child nodes at the same level first, the immediate child nodes will have the smallest distance from the starting node
I believe that the point is that the traversing method has nothing to do with finding shortest path. You can find shortest path using any traversing method. Simply speaking the point was made in one of the previous videos, that BFS can be more optimal for finding shortest path in cases where the target node is a direct child of the node that is currently being considered.
My understanding is that you will get a distances array. And you will have to find the smallest number in the ararry and that would be the shortest path.
BFS works when all the edges have the same distance. Because every single edge has a distance of 6 it's the same as if all of the edges had distance of 1. There would be an issue if different edges had different distances.
shortest reach from where to where is not quite clear.. i see only startid.. since she didn't display whole class code, i'm not sure my question is valid or not but... if 6 is target and startid is 1 in the picture, i think it should be like distance[node] + 1, not EDGE_DISTANCE.. if i'm interviewer, i may ask find shortest path between two node.. then the 1 distance should be added up in each round of for loop to check neighbors.. anyway, most of videos(geeks, byte, leetcode, etc...) that explains BFS used visited[] but using array for distance seems really good idea cause i can use one array for both visited and distance which is cool to me. thanks to her actually.
It was said close to the end of the video, that DFS wouldnt be a good choice for this problem. I have to challenge that. In this particular task we are calculating all the distances to all the nodes from starting node. Both DFS and BFS have the same time and space complexity (its just a stack over queue). Therefore Im making a statement that it would be equally good to use either of them here. What am i missing?
i'm not quite expert but just to share my understanding... still to me BFS is better one for shortest path in time perspective because,, assuming the graph is huge and my target is pretty much close to start but it's in the end of neighbors, then DFS will do search all children in previous neighbors and take whole time to finally find my target..
DFS would fail in the drawn graph here. Let's say our DFS always prioritizes the node with the lowest #. After doing 1, 2, it would do 1, 3, 0, 5, 4. Node 4 would be marked as visited with a distance of 4. After backtracking to 3, it would go to 6 next without visiting 4 again, leaving us with the wrong distance of 4 for Node 4 rather than 2.
Since this is about finding 'shortest' path, BFS is better because if we end up finding the vertex, we would immediately exit, whereas DFS could be really slow if it took the wrong path and explored everything
start to where? what is the purpose hiding other methods? No explanation of overall logic. She just memorized the code and typed it on camera.. worst channel.
What should public Graph(int size), private class Node, private Node getNode(int id), and public void addEdge(int first, int second) look like?
If you are stuck, here's my solution to this (I didn't implement Node class). bit.ly/2E0rfDX
@@zhegemingzigouchang - Why v + 6 ? Doesn't make sense
@@90krishika I would imagine that the +6 is comes from hardcoding the EDGE_DISTANCE static variable from the video.
The link provided in the description is broken: 404 error.
This video is designed for individuals with prior knowledge of BFS and DFS concepts. It serves as a review for those already familiar with these topics, providing an opportunity to reinforce existing understanding. If you are not acquainted with BFS and DFS, it is recommended to gain proficiency in these concepts before engaging with this content.
Please don't just start coding, try to explain the logic first.
😂😂
how would I find the shortest path between two nodes? say I gave two nodes as parameters
you have to track the parent node...
@@Ankit5311 Use LCA.
Do adding 0 in distance array would print that too? Are you eliminating 0 to remove the start node index from the distance and printing it?
it means distance from start node to itself =0,if a cycle is formed we might found distance larger than 0
I think it should be
if((distance[neighbor] < distance[node] + edge) || distance[neighbor] == -1)
Say starting node =1, end node = 4. Now say 1->3 is 10unit and 3->4 is 100unit.
Then using above BFS it will find neighbor of 1 which is 2, 3...then ones it gets to 3 it'll find neighbor 0, 4, 6 and will update distance[4] = 110
But say 3->0 is 10unit and 0 -> 5 10unit and 5 -> 4 is 10 unit. Then once we get to neighbor of 5 the shortest reach using above program will say ohh I already visited "4" (because distance[4] != -1 it's 110) and it will skip updating the distance where it could have been 40Units(1->3 , 3->0, 0->5, 5->4 all 10 units) instead of 110.
what is nodes[node].neighbours ???
neighbors of the node..connected nodes .. a list may be
Must be hidden in the "Node" data structure, something not covered in the video.
yea she folds the Node class you can see its truncated in the ide
The class "Node" has a LinkedList of neighbors. These are the nodes connected to current node. She included the implementation on her video titled: "Algorithms: Graph Search, DFS and BFS."
What she didn't cover is how to create the graphs so that you could test your implementation. For this, you need two methods: 1) One to add Node objects to the Node array (on the other video, she used a Linked List and called it something different) and 2) the implementation of addEdge(int, int). That implementation is actually quite simple:
public void addEdge(int source, int destination) {
Node s = getNode(source);
// This can return null
Node d = getNode(destination);
// This can return null
s.neigbors.add(d);
d.neigbors.add(s);
}
you could avoid returning null by using the Null Object pattern and have the getNode method return a null Node Object rather than a null pointer. Then, you need to connect nodes that are not instances of Null Node class. But this is a topic for another time.
Also, d.neigbors.add(s) should be done only if you want bidirectional routes from node to node. Perhaps it is better to do without this step and add the edges when you create the graph, i.e. graph.addEdge(1, 2) and graph.addEdge(2, 1)
. This way, you could make certain paths unidirectional and other bidirectional if needed.
It will not work on weighted graph, when different edges have diff weights.
yeah cause bfs is not applied for weighted graphs
was wondering if you could help me with a Maze program in java im working on, I'm trying to use a BFS to find the shortestPath and could really use your help :)
Thank you very much ! Great idea to optimize by not keeping the visited array :)
How does BFS gives shortest path ?
Since the graph is not weighted and bfs traverses all the child nodes at the same level first, the immediate child nodes will have the smallest distance from the starting node
I believe that the point is that the traversing method has nothing to do with finding shortest path. You can find shortest path using any traversing method. Simply speaking the point was made in one of the previous videos, that BFS can be more optimal for finding shortest path in cases where the target node is a direct child of the node that is currently being considered.
My understanding is that you will get a distances array. And you will have to find the smallest number in the ararry and that would be the shortest path.
Its been 6 years, how you guys doing? Any update brothers 😂
Dijkstra?
For anyone who did not get how graph is represented in this coding question!
www.hackerrank.com/challenges/ctci-bfs-shortest-reach?h_r=internal-search
You have initialized EDGE_DISTANCE as 6. Isn't BFS shortest distance works when edge distance is 1?
BFS works when all the edges have the same distance. Because every single edge has a distance of 6 it's the same as if all of the edges had distance of 1. There would be an issue if different edges had different distances.
@@primosdelbarrio Ok. I thought DFS works when all edges have weight 1. Thanks
very wonderfully done....thank you.....
shortest reach from where to where is not quite clear.. i see only startid.. since she didn't display whole class code, i'm not sure my question is valid or not but... if 6 is target and startid is 1 in the picture, i think it should be like distance[node] + 1, not EDGE_DISTANCE.. if i'm interviewer, i may ask find shortest path between two node.. then the 1 distance should be added up in each round of for loop to check neighbors.. anyway, most of videos(geeks, byte, leetcode, etc...) that explains BFS used visited[] but using array for distance seems really good idea cause i can use one array for both visited and distance which is cool to me. thanks to her actually.
Seems like memorized solution. I’d never go straight to the code without solving the problem on paper first.
It was said close to the end of the video, that DFS wouldnt be a good choice for this problem. I have to challenge that. In this particular task we are calculating all the distances to all the nodes from starting node. Both DFS and BFS have the same time and space complexity (its just a stack over queue). Therefore Im making a statement that it would be equally good to use either of them here. What am i missing?
i'm not quite expert but just to share my understanding... still to me BFS is better one for shortest path in time perspective because,, assuming the graph is huge and my target is pretty much close to start but it's in the end of neighbors, then DFS will do search all children in previous neighbors and take whole time to finally find my target..
DFS would fail in the drawn graph here. Let's say our DFS always prioritizes the node with the lowest #. After doing 1, 2, it would do 1, 3, 0, 5, 4. Node 4 would be marked as visited with a distance of 4. After backtracking to 3, it would go to 6 next without visiting 4 again, leaving us with the wrong distance of 4 for Node 4 rather than 2.
Since this is about finding 'shortest' path, BFS is better because if we end up finding the vertex, we would immediately exit, whereas DFS could be really slow if it took the wrong path and explored everything
If you're a beginner trying to understand BFS, this is not the place
start to where? what is the purpose hiding other methods? No explanation of overall logic. She just memorized the code and typed it on camera.. worst channel.
Heard some doggos at 4:42
Why is the Linkedlist called a queue :-)
Because is has a head and a tail.
good job gayle laakmann!!!!!!!!1
what is the IDE you are using ?
logic is working.
isn't this Dijkstra?
fiquei na mesma dps deste video
Please share your code?