Search code examples
algorithmgraph-theorybreadth-first-searchshortest-path

How to find all shortest paths

I have a graph and I want to find all shortest paths between two nodes. I've found a shortest path between two nodes by BFS. However, it just gives me one of the shortest paths if there exists one more than.

How could I get all of them using BFS?

I've implement my code from well-known BFS pseudocode.
Also, I have a adjacency list vector which holds adjacency vertices for all nodes.

Solution

  • A simpler way is to find all paths from source to destination using dfs. Now find the shortest paths among these paths. Here is a sudo code:

    dfs(p,len)
      if(visited[p])
         return

      if(p== destination)
          paths.append(len)

          return
      visited[p]=1
      for each w adjacent to p
           dfs(w,len+1)
      visited[p]=0

    You can find the path by maintaining an array for paths. I will leave that to you as an assignment