蟒迪杰斯特拉ķ最短路径(Python Dijkstra k shortest paths)

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

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

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

哪里：

图字典键是一个节点
subdict键是2个节点之间的边
subdict值是边缘权重

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

所以，我移动到达维德爱泼斯坦这里描述的算法http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ （甚至更好的实现可能是与的使用意见发现有heapq）

它的伟大工程，这是非常快的，但我只得到了最好的途径，而不是所有可能的路由列表。而这正是我坚持。

可能有人帮助我与请，或至少给一个方向？我不是在图中的最短路径算法非常好。

提前致谢！

Answer 1:

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

算法

从起点开始运行Dijkstra算法，并获得迪斯[I]列表（出发点和点i之间的最短距离）。然后从终点运行Dijkstra算法，并获得DIST [I]列表（终点和点i之间的最短距离）
创建一个新的图形：在原始图中的边缘，如果迪斯[A] + DIST [B] + W（A，B）==迪斯[终点]，我们添加新图的边缘。这显然是新的图形是一个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, [])