12

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

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

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 值是边缘权重

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

所以我转向大卫爱泼斯坦描述的算法http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/（甚至更好的实现可以在评论中找到使用堆）

它工作得很好，真的很快，但我只得到最好的路线，而不是所有可能路线的列表。这就是我坚持的地方。

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

提前致谢！

4

3 回答 3

9

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

算法

  1. 从起点运行 Dijkstra 算法，得到 disS[i] 列表（起点到点 i 的最短距离）。然后从终点运行 Dijkstra 算法，得到 disT[i] 列表（终点到点 i 的最短距离）
  2. 制作一个新图：对于原图中的一条边，如果 disS[a] + disT[b] + w(a, b) == disS[endpoint]，我们在新图中添加一条边。很明显，新图是一个 DAG（有向无环图），并且有一个 sink（起点）和一个 target（终点）。从接收器到目标的任何路径都是原始图中的最短路径。
  3. 您可以在新图表中运行 DFS。在递归和回溯中保存路径信息，任何时候到达目标，保存的信息都是一条最短路径。算法何时结束完全取决于您。

伪代码：</h2> 
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, [])

于 2012-11-23T03:34:34.237 回答
4

Networkx 具有执行此操作的功能all_shortest_paths。

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

于 2012-11-22T19:50:03.263 回答
0

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

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

于 2013-01-13T21:13:19.220 回答