I'm trying to make a small public transport routing application.
My data is represented in a following structure:
graph = {'A': {'B':3, 'C':5},
'B': {'C':2, 'D':2},
'C': {'D':1},
'D': {'C':3},
'E': {'F':8},
'F': {'C':2}}
Where:
I was using find_shortest_path algorithm described here https://www.python.org/doc/essays/graphs/ but it is rather slow because of recursion and has no support of weights.
So I moved to the algorithm described by Davide Epstein here http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ (and even better implementation could be find there in comments with the usage of heapq)
It works great, it is really fast, but I get only the best route instead of the list of all possible routes. And that is where I stuck.
Could somebody help me with that please, or at least give a direction? I'm not very good in graph shortest paths algorithms.
Thanks in advance!
It's no doubt that there would be a huge amount of shortest paths in the graph. So it is hard to generate all shortest path in a satisfied time-complexity. But I can give you a simple method that can get as much shortest paths as you want.
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, [])