How to find all shortest paths

Question

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.

Answer 1

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