Python Dijkstra k最短路径

小编典典

Python Dijkstra k最短路径

python

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

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

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

哪里：

图dict键是一个节点
下标键是2个节点之间的边
下标值是边缘权重

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

因此，我转到了Davide
Epstein在此处描述的算法，网址为http://code.activestate.com/recipes/119466-dijkstras-
algorithm-for-shortest-
paths/（甚至在使用的注释中可以找到更好的实现） heapq）

它运作良好，速度非常快，但我只能得到最佳路线，而不是所有可能路线的清单。那就是我坚持的地方。

有人可以帮我吗，或者至少给个方向？我在图形最短路径算法方面不是很好。

提前致谢！

阅读 215

2021-01-20

共1个答案

小编典典

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

算法

从起点运行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) #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, [])

2021-01-20