毫无疑问，图中将存在大量最短的路径。因此，很难在令人满意的时间复杂度内生成所有最短路径。但是我可以给你一个简单的方法，它可以根据需要获得尽可能多的最短路径。
算法
- 从起点运行Dijkstra算法，并获得disS [i]列表（起点与点i之间的最短距离）。然后从终点运行Dijkstra算法，并获得disT [i]列表（终点到i点之间的最短距离）
- 制作一个新图形：对于原始图形中的一条边，如果disS [a] + disT [b] + w（a，b）== disS [endpoint]，我们在新图形中添加一条边。显然，新图是DAG（有向无环图），并且具有接收器（起点）和目标（终点）。从汇到目标的任何路径都将是原始图中的最短路径。
- 您可以在新图中运行DFS。在递归和回溯中保存路径信息，只要您到达目标，保存的信息将是最短的路径。算法何时结束完全取决于您。
伪代码：
def find_one_shortest_path(graph, now, target, path_info): if now == target: print path_info return for each neighbor_point of graph[now]: path_info.append(neighbor_point) find_one_shortest_path(graph, neighbor_point, target, path_info) #recursion path_info.pop(-1) #backtrackingdef all_shortest_paths(graph, starting_point, ending_point): disS = [] # shortest path from S disT = [] # shortest path from T new_graph = [] disS = Dijkstra(graph, starting_point) disT = Dijkstra(graph, endinng_point) for each edge<a, b> in graph: if disS[a] + w<a, b> + disT[b] == disS[ending_point]: new_graph.add(<a, b>) find_one_shortest_path(new_graph, starting_point, ending_point, [])
