Python Dijkstra k最短路径

Question

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

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

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

哪里:

1. 图形dict键是一个节点
2. subdict键是2个节点之间的边
3. 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)

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

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

提前致谢!

Answer 1

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

算法

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, [])