Python Dijkstra k shortest paths

Question

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:

1. graph dict key is a node
2. subdict key is an edge between 2 nodes
3. subdict value is an edge weight

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!

Answer 1

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.

Algorithm

1. Run Dijkstra algorithm from starting point, and get disS[i] list(the shortest distance between starting point and point i). And then run Dijkstra algorithm from ending point, and get disT[i] list(the shortest distance between ending point and point i)
2. Make a new graph: for a edge in the original graph, if disS[a] + disT[b] + w(a, b) == disS[ending point], we add a edge in new graph. It's obviously that the new graph is a DAG(Directed acyclic graph), and has a sink(starting point) and a target(ending point). Any path from sink to the target would be a shortest path in the original graph.
3. You can run DFS in the new graph. Save the path information in the recursion and backtracking, any time you reach the target, the saved information would be one shortest path. When the algorithm ending is all depend on you.

Pseudo Code：

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, []) 

Answer 2

I've run across a similar problem in transportation network analysis. I've used the excellent python module NetworkX. It has a function to generate all simple paths between two nodes. Here is the link:

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

Answer 3

Networkx has a function to do this all_shortest_paths.

It returns a generator of all shortest paths.