How to find all shortest paths

15,306

Solution 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

Solution 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 

Solution 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()
    
Share:
15,306
caesar
Author by

caesar

Updated on June 04, 2022

Comments

  • caesar
    caesar over 1 year

    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.

  • Pham Trung
    Pham Trung almost 10 years
    Sorry, but this is wrong, you can not use dfs to find all paths from source to target. For example you will miss one of the two cases: 1->2->3->4 and 1->3->4. If you want to find "all" path, a recursive will be required, not dfs.
  • Pham Trung
    Pham Trung almost 10 years
    By the way,this quesion is duplicated stackoverflow.com/questions/14144071/…
  • caesar
    caesar almost 10 years
    thanks to you, I got parents information correctly,however,I have no idea how could I print path by backtracing without recursion, do you have any hint ?
  • soup_boy
    soup_boy almost 10 years
    yes, you can use a stack and do it iteratively. I will post the pseudocode shortly.
  • Bernhard Barker
    Bernhard Barker almost 10 years
    Note that this is a very inefficient way of doing things. Consider a graph with a billion nodes and the shortest path between the two target nodes is of length 5. You'll be exploring all the nodes rather than just those distance 5 from the source node. Modified BFS is a lot better.
  • Bernhard Barker
    Bernhard Barker almost 10 years
    @PhamTrung DFS is recursive. For the 1 node, it will first go to 2, and find 1->2->3->4 and then it will backtrack back to 1 and go to 3 and find 1->3->4. And you duplicate comment would probably have been better suited as a comment on the question or a duplicate flag (I just flagged it).
  • Pham Trung
    Pham Trung almost 10 years
    @Dukeling, What i mean is complete search by recursive :) sorry, this code is not dfs, i misunderstood it :D and storing path in array is not a good idea as the path can already contain the current node, which need a further check
  • soup_boy
    soup_boy almost 10 years
    The answer posted by banarun will work for printing all the paths. Use the parent vectors instead of the adjacency list. Start from the destination and trace all the paths to the starting node.