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

Answer 2

You can easily do it by maintaining a list or vector of parents for each node. If two or more nodes ( say X, Y, Z) at the same distance from the starting node , leads to another node M , make all X , Y and Z as the parents of M.

You just have to add a check to see while adding a parent to the node whether that parent is in the same level as the previous parents.

By level , I mean the distance from the starting point.

This way you can get all the shortest paths by tracing back the parent vectors. Below is my C++ implementation.

I hope you know how to print the paths by starting from the destination ,tracing the parents and reach the starting point.

EDIT : Pseudo Code

bfs (start , end)

    enqueue(start)
    visited[start] = 1

    while queue is NOT empty

        currentNode = queue.front()
        dequeue()

        if(currentNode == end)
            break

        for each node adjacent to currentNode

            if node is unvisited
                visited[node] = visited[curr] + 1
                enqueue(node)
                parent[node].add(currentNode)

            else if(currentNode is in same level as node's parents)
                parent[node].add(currentNode)

return 

Answer 3

If the graph is large, finding all paths from start to end and then selecting the shortest ones can be very inefficient. Here is a better algorithm:

1. Using BFS, label each node with its distance from the start node. Stop when you get to the end node.

   def bfs_label(start, end):
       depth = {start: 0}
       nodes = [start]
       while nodes:
           next_nodes = []
           for node in nodes:
               if node == end:
                   return depth
   
           for neighbor in neighbors(node):
               if neighbor not in depth:
                   depth[neighbor] = depth[node] + 1
                   fringe.append(neighbor)
   

2. Using DFS, find all paths from the start node to the end node such that the depth strictly increases for each step of the path.

   def shortest_paths(node, end, depth, path=None):
       if path is None:
           path = []
   
       path.append(node)
   
       if node == end:
           yield tuple(path)
       else:
           for neighbor in neighbors(node):
               if neighbor in depth and depth[neighbor] == depth[node]+1:
                   for sp in shortest_paths(neighbor, end, depth, path):
                       yield sp
   
       path.pop()
   

Answer 4

We can use a simple BFS algorithm for finding all the shortest paths. We can maintain the path along with the current node. I have provided the link to the python code for the same below. https://gist.github.com/mridul111998/c24fbdb46492b57f7f17decd8802eac2