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. graph dict key是一个节点
2. 细分键是两个节点之间的边
3. 细分值是边权重

我使用的是这里描述的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（有向无环图），有一个sink（起点）和一个target（终点）。从sink到目标的任何路径都是原始图中的最短路径。
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, []) 

Answer 2

Networkx有一个函数来完成这个任务all_shortest_paths。

它返回所有最短路径的生成器。

Answer 3

我在交通网络分析中遇到过类似的问题。我使用了优秀的python模块NetworkX。它具有在两个节点之间生成所有简单路径的功能。以下是链接：

http://networkx.lanl.gov/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html