Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Python Dijkstra k shortest paths

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!

like image 439
Volodymyr Smirnov Avatar asked Nov 22 '12 19:11

Volodymyr Smirnov


People also ask

Can Dijkstra find all shortest paths?

With Dijkstra's Algorithm, you can find the shortest path between nodes in a graph. Particularly, you can find the shortest path from a node (called the "source node") to all other nodes in the graph, producing a shortest-path tree.

Is A * better than Dijkstra?

In general A* is more performant than Dijkstra's but it really depends the heuristic function you use in A*. You'll want an h(n) that's optimistic and finds the lowest cost path, h(n) should be less than the true cost. If h(n) >= cost, then you'll end up in a situation like the one you've described.


1 Answers

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, []) 
like image 139
Jun HU Avatar answered Sep 27 '22 19:09

Jun HU