毫无疑问,图中将存在大量最短的路径。因此,很难在令人满意的时间复杂度内生成所有最短路径。但是我可以给你一个简单的方法,它可以根据需要获得尽可能多的最短路径。
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) #backtracking
def 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, [])