logo标签列表

Python Dijkstra算法求k条最短路径

pythonalgorithmgraphgraph-algorithmdijkstra
11

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

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

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

其中：

  1. 图字典中的键是节点
  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的用法）

它运行得很好，非常快，但我只得到了最佳路线而不是所有可能路线的列表。那就是我卡住的地方。

请问有人能帮我解决这个问题吗，或者至少给一个方向？我不太擅长图形最短路径算法。

谢谢！

1
我不确定我是否理解您要查找的内容。您是想在各个节点对之间找到多条最短路径，还是针对单个节点对想要多条路径？ - Blckknght
1
Blckknght，我需要一个单一对的多条路径。上面提到的算法只返回“最佳”路径，而不是“所有可能”的路径。 - Volodymyr Smirnov
1
Dijkstra算法旨在找到最短路径，因此我认为这对你来说不会有什么用处。我怀疑某种深度优先遍历可能是你的最佳选择，而且我不知道它是否比你第一个链接中的代码更快（尽管那段代码有一些丑陋的部分，如可变默认参数）。 - Blckknght
3个回答
8

毫无疑问，图中会有大量的最短路径。因此，在满足时间复杂度的情况下生成所有最短路径是很困难的。但我可以给你一个简单的方法，可以获取尽可能多的最短路径。

算法

  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, [])
4
Networkx有一个函数可以实现这个功能all_shortest_paths。它返回所有最短路径的生成器。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接