如何找到所有最短路径

Question

我有一张图，想要找到两个节点之间的所有最短路径。我已经通过BFS找到了两个节点之间的一条最短路径。但是，如果存在多条最短路径，则只给出其中一条。

如何使用BFS获取所有最短路径？

我已经按照众所周知的BFS伪代码实现了我的代码。此外，我有一个邻接列表向量，它保存了所有节点的邻接顶点。

- caesar

---

@Dukeling 谢谢回复。我不想找到所有顶点之间的所有路径。我想要找到的是两个特定节点之间的所有最短路径。 - caesar

你应该发布你的实际代码，而不是伪代码。 - Retired Ninja

@RetiredNinja 既然这是一个作业，我不应该在这里放上它。 - caesar

这类似于动态规划，假设最短距离为x，从起始节点开始，您可以前往每个距目标距离为x-1的相邻节点，并继续递归。完成！ - Pham Trung

你可以使用深度优先搜索（DFS）来找到从A到B的所有路径。按照路径长度进行排序，然后你就能找到所有最短路径了。 - banarun

可能是在无权无向图中查找两个节点之间所有最短路径的问题的重复。 - Bernhard Barker

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 

- soup_boy

---

感谢您，我已经正确地获取了父节点信息，但是我不知道如何在没有递归的情况下通过回溯打印路径，您有什么提示吗？ - caesar

是的，您可以使用堆栈并进行迭代。我很快会发布伪代码。 - soup_boy

banarun发布的答案可以用于打印所有路径。使用父向量而不是邻接列表。从目标开始，跟踪到起始节点的所有路径。 - soup_boy

Answer 2

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

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()
   

- augurar

Answer 3

一种更简单的方法是使用深度优先搜索查找源到目标的所有路径。现在在这些路径中找到最短路径。以下是伪代码：

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

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

- banarun

---

抱歉，但这是错误的，你不能使用深度优先搜索来查找从源到目标的所有路径。例如，你会错过1->2->3->4和1->3->4两种情况中的其中一种。如果你想要找到“所有”路径，需要使用递归，而不是dfs。 - Pham Trung

顺便提一下，这个问题已经重复了 https://dev59.com/nGYq5IYBdhLWcg3w2UIU?rq=1 - Pham Trung

请注意，这种做法非常低效。考虑一个具有十亿个节点的图形，两个目标节点之间的最短路径长度为5。您将探索所有节点，而不仅仅是距离源节点5个单位的节点。修改后的广度优先搜索（Modified BFS）要好得多。 - Bernhard Barker

@PhamTrung DFS是递归的。对于节点1，它首先会到达2，并找到1->2->3->4，然后回溯回到1，再到3并找到1->3->4。而您的重复评论可能更适合作为问题的评论或重复标记（我刚刚已经标记了它）。 - Bernhard Barker

@Dukeling，我的意思是通过递归进行完整搜索 :) 抱歉，这段代码不是深度优先搜索，我误解了它:D 将路径存储在数组中并不是一个好主意，因为路径可能已经包含当前节点，需要进一步检查。 - Pham Trung

Answer 4

我们可以使用简单的BFS算法来查找所有最短路径。我们可以维护路径以及当前节点。我在下面提供了相应的Python代码链接。 https://gist.github.com/mridul111998/c24fbdb46492b57f7f17decd8802eac2

- MRIDUL SHARMA