我正在尝试制作一个小型公共交通路线应用程序。
我的数据以下列结构表示：
graph = {'A': {'B':3, 'C':5},
'B': {'C':2, 'D':2},
'C': {'D':1},
'D': {'C':3},
'E': {'F':8},
'F': {'C':2}}
哪里：
- 图dict键是一个节点
- subdict键是2个节点之间的边
- subdict值是边权重
我正在使用这里描述的find_shortest_path算法 https://www.python.org/doc/essays/graphs/ 但由于递归而且它没有重量支持，所以它相当慢。
所以我转到了Davide Epstein所描述的算法 http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ （甚至更好的实现可以在使用heapq的注释中找到）
它工作得很好，它真的很快，但我只获得最佳路线而不是所有可能路线的列表。这就是我陷入困境的地方。
有人可以帮助我，或至少给出指示？我在图最短路径算法方面不是很好。
提前致谢！
毫无疑问，图中会有大量的最短路径。因此很难在满足时间复杂度的情况下生成所有最短路径。但我可以给你一个简单的方法，可以获得你想要的最短路径。
算法
- 从起点运行Dijkstra算法，得到disS [i]列表（最短距离
起点和点之间i）。然后从终点运行Dijkstra算法，得到disT [i]列表（终点和点i之间的最短距离）
- 创建一个新图形：对于原始图形中的边缘，如果
disS [a] + disT [b] + w（a，b）== disS [终点]，我们在新图中添加边。显然，新图是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, [])
Networkx具有执行此操作的功能 all_shortest_paths。
它返回所有最短路径的生成器。