How does a Breadth-First Search work when looking for Shortest Path

Question

I ve done some research  and I seem to be missing one small part of this algorithm  I understand how a Breadth-First Search works  but I don t understand how exactly it will get me to a specific path  as opposed to just telling me where each individual node can go  I guess the easiest way to explain my confusion is to provide an example   So for instance  let s say I have a graph like this     And my goal is to get from A to E  all edges are unweighted    I start at A  because that s my origin  I queue A  followed by immediately dequeueing A and exploring it  This yields B and D  because A is connected to B and D  I thus queue both B and D   I dequeue B and explore it  and find that it leads to A  already explored   and C  so I queue C  I then dequeue D  and find that it leads to E  my goal  I then dequeue C  and find that it also leads to E  my goal   I know logically that the fastest path is A- D- E  but I m not sure how exactly the breadth-first search helps - how should I be recording paths such that when I finish  I can analyze the results and see that the shortest path is A- D- E   Also  note that I m not actually using a tree  so there are no  parent  nodes  only children

User · Answer

Visiting this thread after some period of inactivity, but given that I don't see a thorough answer, here's my two cents.

Breadth-first search will always find the shortest path in an unweighted graph. The graph may be cyclic or acyclic.

See below for pseudocode. This pseudocode assumes that you are using a queue to implement BFS. It also assumes you can mark vertices as visited, and that each vertex stores a distance parameter, which is initialized as infinity.

mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 0
if the start vertex is the end vertex, return 0
push the start vertex on the queue
while(queue is not empty)   
    dequeue one vertex (we’ll call it x) off of the queue
    if x is not marked as visited:
        mark it as visited
        for all of the unmarked children of x:
            set their distance values to be the distance of x + 1
            if the value of x is the value of the end vertex: 
                return the distance of x
            otherwise enqueue it to the queue
if here: there is no path connecting the vertices

Note that this approach doesn't work for weighted graphs - for that, see Dijkstra's algorithm.

User · Answer

From tutorial here      It has the extremely useful property that if all of the edges in a graph are unweighted  or the same weight  then the first time a node is visited is the shortest path to that node from the source node

User · Answer

A good explanation of how BFS computes shortest paths  accompanied by the most efficient simple BFS algorithm of which I m aware and also by working code  is provided in the following peer-reviewed paper  https   queue acm org detail cfm id 3424304 The paper explains how BFS computes a shortest-paths tree represented by per-vertex parent pointers  and how to recover a particular shortest path between any two vertices from the parent pointers   The explanation of BFS takes three forms  prose  pseudocode  and a working C program  The paper also describes  quot Efficient BFS quot   E-BFS   a simple variant of classic textbook BFS that improves its efficiency   In the asymptotic analysis  running time improves from Theta V E  to Omega V    In words  classic BFS always runs in time proportional to the number of vertices plus the number of edges  whereas E-BFS sometimes runs in time proportional to the number of vertices alone  which can be much smaller   In practice E-BFS can be much faster  depending on the input graph   E-BFS sometimes offers no advantage over classic BFS but it s never much slower  Remarkably  despites its simplicity E-BFS appears not to be widely known

User · Answer

As pointed above  BFS can only be used to find shortest path in a graph if    There are no loops All edges have same weight or no weight    To find the shortest path  all you have to do is start from the source and perform a breadth first search and stop when you find your destination Node  The only additional thing you need to do is have an array previous n  which will store the previous node for every node visited  The previous of source can be null    To print the path  simple loop through the previous   array from source till you reach destination and print the nodes  DFS can also be used to find the shortest path in a graph under similar conditions   However  if the graph is more complex  containing weighted edges and loops  then we need a more sophisticated version of BFS  i e  Dijkstra s algorithm

User · Answer

The following solution works for all the test cases   import java io    import java util    import java text    import java math    import java util regex     public class Solution       public static void main String   args                        Scanner sc   new Scanner System in                int testCases   sc nextInt                 for  int i   0  i  lt  testCases  i                                  int totalNodes   sc nextInt                    int totalEdges   sc nextInt                     Map lt Integer  List lt Integer gt  gt  adjacencyList   new HashMap lt Integer  List lt Integer gt  gt                      for  int j   0  j  lt  totalEdges  j                                          int src   sc nextInt                        int dest   sc nextInt                         if  adjacencyList get src     null                                                List lt Integer gt  neighbours   new ArrayList lt Integer gt                             neighbours add dest                           adjacencyList put src  neighbours                         else                                               List lt Integer gt  neighbours   adjacencyList get src                           neighbours add dest                           adjacencyList put src  neighbours                                               if  adjacencyList get dest     null                                                List lt Integer gt  neighbours   new ArrayList lt Integer gt                             neighbours add src                           adjacencyList put dest  neighbours                         else                                               List lt Integer gt  neighbours   adjacencyList get dest                           neighbours add src                           adjacencyList put dest  neighbours                                                            int start   sc nextInt                     Queue lt Integer gt  queue   new LinkedList lt  gt                      queue add start                    int   costs   new int totalNodes   1                    Arrays fill costs  0                    costs start    0                   Map lt String  Integer gt  visited   new HashMap lt String  Integer gt                      while   queue isEmpty                                          int node   queue remove                         if visited get node         null                                                continue                                             visited put node       1                        int nodeCost   costs node                        List lt Integer gt  children   adjacencyList get node                        if  children    null                                                for  Integer child   children                                                        int total   nodeCost   6                              String key   child                                    if  visited get key     null                                                                queue add child                                    if  costs child     0                                                                        costs child    total                                    else if  costs child   gt  total                                                                        costs child    total                                                                                                                                                     for  int k   1  k  lt   totalNodes  k                                          if  k    start                                                continue                                             System out print costs k     0   -1   costs k                        System out print                                         System out println

User · Answer

Based on acheron55 answer I posted a possible implementation here   Here is a brief summery of it     All you have to do  is to keep track of the path through which the target has been reached   A simple way to do it  is to push into the Queue the whole path used to reach a node  rather than the node itself   The benefit of doing so is that when the target has been reached the queue holds the path used to reach it   This is also applicable to cyclic graphs  where a node can have more than one parent

User · Answer

Technically  Breadth-first search  BFS  by itself does not let you find the shortest path  simply because BFS is not looking for a shortest path  BFS describes a strategy for searching a graph  but it does not say that you must search for anything in particular   Dijkstra s algorithm adapts BFS to let you find single-source shortest paths   In order to retrieve the shortest path from the origin to a node  you need to maintain two items for each node in the graph  its current shortest distance  and the preceding node in the shortest path  Initially all distances are set to infinity  and all predecessors are set to empty  In your example  you set A s distance to zero  and then proceed with the BFS  On each step you check if you can improve the distance of a descendant  i e  the distance from the origin to the predecessor plus the length of the edge that you are exploring is less than the current best distance for the node in question  If you can improve the distance  set the new shortest path  and remember the predecessor through which that path has been acquired  When the BFS queue is empty  pick a node  in your example  it s E  and traverse its predecessors back to the origin  This would give you the shortest path   If this sounds a bit confusing  wikipedia has a nice pseudocode section on the topic

User · Answer

I have wasted 3 days ultimately solved a graph question used for finding shortest distance using BFS    Want to share the experience   When the  undirected for me  graph has fixed distance  1  6  etc   for edges   1 We can use BFS to find shortest path simply by traversing it then  if required  multiply with fixed distance  1  6  etc     2 As noted above with BFS the very 1st time an adjacent node is reached  it is shortest path   3 It does not matter what queue you use    deque queue c    or    your own queue implementation  in c language     A circular queue is unnecessary   4 Number of elements required for queue is N 1 at most  which I used  dint check if N works  here  N is V  number of vertices    5 Wikipedia BFS will work  and is sufficient      https   en wikipedia org wiki Breadth-first search Pseudocode   I have lost 3 days trying all above alternatives  verifying  amp  re-verifying again and again above they are not the issue   Try to spend time looking for other issues  if you dint find any issues with above 5      More explanation from the comment below         A             B       C              D  E     F  G   Assume above is your graph graph goes downwards For A  the adjacents are B  amp  C For B  the adjacents are D  amp  E For C  the adjacents are F  amp  G    say  start node is A     when you reach A  to  B  amp  C the shortest distance to B  amp  C from A is 1   when you reach D or E  thru B   the shortest distance to A  amp  D is 2  A- B- D      similarly  A- E is 2   A- B- E     also  A- F  amp  A- G is 2    So  now instead of 1 distance between nodes  if it is 6  then just multiply the answer by 6 example  if distance between each is 1  then   A- E is 2    A- B- E   1 1  if distance between each is 6  then   A- E is 12   A- B- E   6 6     yes  bfs may take any path but we are calculating for all paths    if you have to go from A to Z  then we travel all paths from A to an intermediate I  and since there will be many paths we discard all but shortest path till I  then continue with shortest path ahead to next node J again if there are multiple paths from I to J  we only take shortest one example  assume  A -  I we have distance 5  STEP  assume  I -  J we have multiple paths  of distances 7  amp  8  since 7 is shortest we take A -  J as 5  A- I shortest    8  shortest now    13 so A- J is now 13 we repeat now above  STEP  for J -  K and so on  till we get to Z    Read this part  2 or 3 times  and draw on paper  you will surely get what i am saying  best of luck

[java] How does a Breadth-First Search work when looking for Shortest Path?

Examples related to java

Examples related to shortest-path

Examples related to breadth-first-search