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

help
, , , ,
1

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

1 Like
2

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.*

3

Heres the problem in which you need to find minimum distance using BFS : Breadth First Search: Shortest Reach | HackerRank

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

4

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

5

please provide me code with explanation

6

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

7

please explain your code,by comments.

8

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

9

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