Python Dijkstra k最短路径

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python Dijkstra k最短路径，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1973字，纯文字阅读大概需要3分钟。

内容图文

我正在尝试制作一个小型公共交通路线应用程序.

我的数据以下列结构表示：

graph = {'A': {'B':3, 'C':5},
     'B': {'C':2, 'D':2},
     'C': {'D':1},
     'D': {'C':3},
     'E': {'F':8},
     'F': {'C':2}}

哪里：

>图表dict键是一个节点
> subdict键是2个节点之间的边
> subdict value是边权重

我正在使用这里描述的find_shortest_path算法https://www.python.org/doc/essays/graphs/,但由于递归而且它不支持权重,所以它相当慢.

所以我转到了Davide Epstein在这里描述的算法http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/(甚至更好的实现可以在使用heapq的评论中找到)

它工作得很好,它真的很快,但我只获得最佳路线而不是所有可能路线的列表.这就是我陷入困境的地方.

有人可以帮助我,或者至少给出指示？我在图最短路径算法方面不是很好.

提前致谢！

解决方法:

毫无疑问,图中会有大量的最短路径.因此很难在满足时间复杂度的情况下生成所有最短路径.但我可以给你一个简单的方法,可以获得你想要的最短路径.

算法

>从起点运行Dijkstra算法,得到disS [i]列表(最短距离
在起点和点之间i).然后从终点运行Dijkstra算法,得到disT [i]列表(终点和点i之间的最短距离)
>制作新图表：对于原始图表中的边缘,如果
disS [a] disT [b] w(a,b)== disS [结束点],我们在新图中添加边.显然,新图是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) #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, []) 

内容总结

以上是互联网集市为您收集整理的Python Dijkstra k最短路径全部内容，希望文章能够帮你解决Python Dijkstra k最短路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端