如何找到所有最短的路径

Question

我有一个图表,我想找到两个节点之间的所有最短路径.我在BFS找到了两个节点之间的最短路径.但是,它只是给我一条最短路径,如果存在一条以上.

我怎么能使用BFS获得所有这些？

我已经从众所周知的BFS伪代码实现了我的代码.
此外,我有一个邻接列表向量,它包含所有节点的邻接顶点.

Answer 1

您可以通过维护每个节点的父级列表或向量来轻松完成此操作.如果距起始节点相同距离的两个或多个节点(比如X,Y,Z)通向另一个节点M,则将所有X,Y和Z作为M的父节点.

您只需添加一个检查,以便在向节点添加父级时查看该父级是否与先前父级处于同一级别.

按级别,我的意思是距离起点的距离.

这样,您可以通过追溯父向量来获取所有最短路径.下面是我的C++实现.

我希望你知道如何从目的地开始打印路径,跟踪父母并到达起点.

编辑:伪代码

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 2

如果图很大，找到从头到尾的所有路径，然后选择最短的路径可能非常低效。这是一个更好的算法：

1. 使用 BFS，用它与起始节点的距离标记每个节点。到达结束节点时停止。

   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. 使用 DFS，找到从起始节点到结束节点的所有路径，使得路径的每一步深度都严格增加。

   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 3

更简单的方法是使用 dfs 查找从源到目的地的所有路径。现在找出这些路径中的最短路径。这是一个 sudo 代码：

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

您可以通过维护路径数组来找到路径。我会把它作为一项任务留给你