Algorithms: Solve 'Shortest Reach' Using BFS

Learn how to find the shortest path using breadth first search (BFS) algorithm. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

[mudaix]

What should public Graph(int size), private class Node, private Node getNode(int id), and public void addEdge(int first, int second) look like?

[davidwoosley]

The link provided in the description is broken: 404 error.

[onionsandwich]

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.

[pawandeepchor]

Please don't just start coding, try to explain the logic first.

[craiglistmail]

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.

[tirthdoshi]

Thank you very much ! Great idea to optimize by not keeping the visited array :)

[TeeFoles]

how would I find the shortest path between two nodes? say I gave two nodes as parameters

[sukumarkuppusamy]

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?

[LaggLtd]

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 :)

[ahmadsaeed]

It will not work on weighted graph, when different edges have diff weights.

[itsmerajas]

For anyone who did not get how graph is represented in this coding question!

[AD-jzsq]

Seems like memorized solution. I’d never go straight to the code without solving the problem on paper first.

[quangdutran]

If you're a beginner trying to understand BFS, this is not the place

[soumitramehrotra]

You have initialized EDGE_DISTANCE as 6. Isn't BFS shortest distance works when edge distance is 1?

[oceanview-uq]

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.

[TheZwirek]

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?

[larssmeets]

Why is the Linkedlist called a queue :-)

[YT-yt-yt-]

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.