Python Dijkstra k最短路径

Python Dijkstra k最短路径,第1张

Python Dijkstra k最短路径

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

算法
  1. 从起点运行Dijkstra算法,并获得disS [i]列表(起点与点i之间的最短距离)。然后从终点运行Dijkstra算法,并获得disT [i]列表(终点到i点之间的最短距离)
  2. 制作一个新图形:对于原始图形中的一条边,如果disS [a] + disT [b] + w(a,b)== disS [endpoint],我们在新图形中添加一条边。显然,新图是DAG(有向无环图),并且具有接收器(起点)和目标(终点)。从汇到目标的任何路径都将是原始图中的最短路径。
  3. 您可以在新图中运行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, [])


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5508330.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-13
下一篇 2022-12-13

发表评论

登录后才能评论

评论列表(0条)

保存