Geek Answers Handbook

How to find all the shortest paths

I have a graph, and I want to find all the shortest paths between two nodes. I found the shortest path between the two BFS nodes. However, it just gives me one of the shortest paths if there is another one.

How can I get all of them using BFS?

I am implementing my code from the well-known BFS pseudocode.
In addition, I have an adjacency list vector that contains adjacency vertices for all nodes.

+4
source share
3 answers

An easier way is to find all the paths from source to destination using dfs. Now find the shortest paths between these paths. Here is the 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

, .

+1

, node. (, X, Y, Z) node, node M, X, Y Z M.

, , node, , .

.

, , . ++.

, , , , .

:

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 parents)
                parent[node].add(currentNode)

return
+4

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

  • Using BFS, name each node its distance from the beginning of the node. Stop when you get to the end of the 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)

  • Using DFS, find all the paths from the beginning of the node to the end of the node so 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()
0
source

More articles:


All Articles