how can i use bfs to find shortest path?how to apply bfs for finding shortest path between 2 nodes?

why 0-1 bfs gives accurate result as simple bfs not?
please provide me (stl code)for shortest path with bfs.

1 Like

Yes you can use. Here is the link to this problem Solve Breadth First Search:
Shortest Reach If you have ever heard of “print level of vertices in tree/graph” problem, then you can easily relate that problem to this. You just need to bfs traversal, and make sure you are not visiting same node again. And have dist[] array which has shortest distance for all the vertices, initialise dist[src] = 0, and for each vertex update dist[v] = dist[u]+6 . You should be able to solve it.

*Think of it in this way. Let’s say graph represents a map. Nodes are different cities. Let’s assume there is road between each pair of city which is 1 km apart. So map will be a graph with all the edges having weight 1. Now you run BFS and you get shortest path from city A to B. Now if I change my metric of distance from km to m, all the edge weights will become 1000 m (or 1000 for BFS). Will it make any difference to BFS? Nope :slight_smile:

Compare BFS with Djikstra’s algo which is more general version of shortest path algo. Djisktra’s algo uses priority queue to pick up the next edge to explore where as BFS uses normal FIFO queue. The behavior of priority queue and FIFO queue will be similar for any constant weight. So it doesn’t have to be 1, it can be any constant c > 0.*

please provide me code with explanation

Heres the problem in which you need to find minimum distance using BFS : https://www.hackerrank.com/challenges/bfsshortreach

Here’s the solution to it using C++ STL : https://github.com/Shraeyas/General-Codes/blob/master/bfsdis.cpp

nice,can u provide me some more links of graph algo(your repositry links),please

please explain your code,by comments.

It is similar to the bfs which we discussed yesterday.

Just one minor change :
Distance of a node y if we have an edge from x to y will be distance of x currently + distance of y from x

Just this minor addition is there in this code if you compare it to yesterday’s BFS


read this awesome article on 0-1 bfs for more clarification

okay i will try to learn.if any doubts then will ask u