给定一个复杂的图结构，设计一个算法来找出图中任意两个节点之间的所有最短路径。

Question

Accepted Answer

要找出图中任意两个节点之间的所有最短路径，可以采用广度优先搜索（BFS）和回溯法相结合的方法。首先，使用 BFS 来计算从起始节点到所有其他节点的最短距离，同时记录每个节点的所有父节点，这些父节点是在最短路径上到达该节点的前一个节点。以下是 BFS 部分的步骤：1. 初始化一个队列，将起始节点加入队列，并将其距离设为 0。2. 当队列不为空时，取出队列头部的节点，遍历其所有邻接节点。如果邻接节点未被访问过，或者通过当前节点到达邻接节点的距离更短，则更新邻接节点的距离和父节点列表。如果距离相等，则将当前节点加入邻接节点的父节点列表。3. 重复步骤 2，直到队列为空。完成 BFS 后，使用回溯法从目标节点开始，沿着父节点列表回溯到起始节点，生成所有最短路径。以下是 Python 代码示例：
python
from collections import defaultdict, deque

def find_shortest_paths(graph, start, end):
    distance = {start: 0}
    parent = defaultdict(list)
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                parent[neighbor].append(node)
                queue.append(neighbor)
            elif distance[neighbor] == distance[node] + 1:
                parent[neighbor].append(node)
    paths = []
    def backtrack(path):
        node = path[-1]
        if node == start:
            paths.append(path[::-1])
        else:
            for p in parent[node]:
                backtrack(path + [p])
    backtrack([end])
    return paths
该算法的时间复杂度主要取决于图的节点数和边数，为 O(V + E) 进行 BFS，回溯的复杂度与最短路径的数量有关。