Python Dijkstra k 最短路径 [英] Python Dijkstra k shortest paths

问题描述

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

I'm trying to make a small public transport routing application.

我的数据以以下结构表示:

My data is represented in a following structure:

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

地点:

1. graph dict key 是一个节点
2. subdict key 是两个节点之间的边
3. subdict 值是一个边权重

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

I was using find_shortest_path algorithm described here https://www.python.org/doc/essays/graphs/ but it is rather slow because of recursion and has no support of weights.

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

So I moved to the algorithm described by Davide Epstein here http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ (and even better implementation could be find there in comments with the usage of heapq)

效果很好，真的很快，但我只得到最佳路线，而不是所有可能路线的列表.这就是我坚持的地方.

It works great, it is really fast, but I get only the best route instead of the list of all possible routes. And that is where I stuck.

有人可以帮我解决这个问题，或者至少给个方向吗?我不太擅长图最短路径算法.

Could somebody help me with that please, or at least give a direction? I'm not very good in graph shortest paths algorithms.

提前致谢！

推荐答案

毫无疑问，图中会有大量的最短路径.因此很难在满足的时间复杂度下生成所有最短路径.但是我可以给你一个简单的方法，可以得到尽可能多的最短路径.

It's no doubt that there would be a huge amount of shortest paths in the graph. So it is hard to generate all shortest path in a satisfied time-complexity. But I can give you a simple method that can get as much shortest paths as you want.

1. 从起点运行Dijkstra算法，得到disS[i]列表(最短距离在起点和点 i) 之间.然后从终点运行Dijkstra算法，得到disT[i]列表(终点到点i的最短距离)
2. 制作新图:对于原图中的一条边，如果disS[a] + disT[b] + w(a, b) == disS[结束点]，我们在新图中添加一条边.很明显，新图是一个 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) #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 最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！