毫无疑问,图中将存在大量最短的路径。因此,很难在令人满意的时间复杂度内生成所有最短路径。但是我可以给你一个简单的方法,它可以根据需要获得尽可能多的最短路径。
算法- 从起点运行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, [])
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)