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

问题描述

我试图做一个小的公共交通路由的应用程序。

psented在以下结构

我的数据重新$ P $：

 图= {'A​​'：{'B'：3，'C'：5}，
     B：{C：2，D：2}，
     C：{D：1}，
     D：{'C'：3}，
     E：{F：8}，
     F：{C：2}}
 

其中：

1. 在图字典键是一个节点
2. subdict关键是2个节点
之间的边缘
3. subdict值是边缘重量

我用的是这里所描述find_shortest_path算法 https://www.python.org/doc/散文/图表/ 但正是因为递归相当缓慢，并没有支撑权重。

所以，我移动到达维德爱泼斯坦这里的http://$c$c.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ （甚至更好的实施，可以发现有与heapq的使用评论）

它的伟大工程，这是非常快的，但我只得到了最佳路线，而不是所有可能的路由列表。而这正是我卡住了。

可能有人帮我说请，或至少给一个方向？我不是在图中的最短路径算法很不错。

在此先感谢！

解决方案

这是毫无疑问，会有大量的图中的最短路径。因此，很难产生在一个满意的时间复杂度的所有最短路径。但是，我可以给你，只要你想，可以让尽可能多的最短路径的简单方法。

算法

1. 运行Dijkstra算法从起点开始，并获得迪斯[I]列表（最短距离 出发点和点之间的我）。再从终点运行Dijkstra算法，并获得DIST [我]列表
（结束点与点i之间的最短距离）
2. 请新图：在原图的边缘，如果 迪斯[A] + DIST [B] + W（A，B）==迪斯[终点]，我们添加了新的图中的边缘。很显然，新的图是一个DAG（有向无环图），并有一个接收器（起点）和目标（终点）。从汇到目标的任何路径是在原来的图中​​的最短路径。
3. 您可以在新的图形运行DFS。保存的路径信息 递归和回溯，你达到目标的任何时间，保存 信息会为一个最短路径。当算法结局都取决于你。

伪code：

 高清find_one_shortest_path（图，现在的目标，PATH_INFO）：
    如果现在==目标：
        打印PATH_INFO
        返回
    对于图的每一个neighbor_point [现在]：
        path_info.append（neighbor_point）
        find_one_shortest_path（图，neighbor_point，目标，PATH_INFO）#recursion
        path_info.pop（-1）#backtracking

高清all_shortest_paths（图，starting_point，ending_point）：
    迪斯= []＃最短选自S路径
    DIST = []＃最短的从T路径
    new_graph = []
    迪斯= Dijkstra算法（图，starting_point）
    DIST = Dijkstra算法（图，endinng_point）
    对于每条边＆其中;一，B个在图中：
        如果迪斯[A] + W＆LT; A，B＆GT; + DIST [B] ==迪斯[ending_point]：
            new_graph.add（小于A，B＆GT;）
    find_one_shortest_path（new_graph，starting_point，ending_point，[]）
 

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}}

Where:

1. graph dict key is a node
2. subdict key is an edge between 2 nodes
3. subdict value is an edge weight

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.

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.

Thanks in advance!

解决方案

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.

Algorithm

1. Run Dijkstra algorithm from starting point, and get disS[i] list(the shortest distance between starting point and point i). And then run Dijkstra algorithm from ending point, and get disT[i] list(the shortest distance between ending point and point i)
2. Make a new graph: for a edge in the original graph, if disS[a] + disT[b] + w(a, b) == disS[ending point], we add a edge in new graph. It's obviously that the new graph is a DAG(Directed acyclic graph), and has a sink(starting point) and a target(ending point). Any path from sink to the target would be a shortest path in the original graph.
3. You can run DFS in the new graph. Save the path information in the recursion and backtracking, any time you reach the target, the saved information would be one shortest path. When the algorithm ending is all depend on you.

Pseudo Code：

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ķ最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！