1

I have a very large network (road network from an entire country) which I load into networkx to calculate distances between points. This works fine and is very fast if I just want to know the fastest route between two points. However, I want to know route alternatives as well (if one route is for example 1000km, I want to know the alternative of 1010, 1018, 1032 and 1042km as well). I thought of using the all_simple_paths function of networkx, but this is really slow and will take days to run. Can anybody suggest an alternative approach?

Thanks!

Yorian
  • 2,002
  • 5
  • 34
  • 60

1 Answers1

2

Networkx has a built in algorithm that generates the shortest path, then the next shortest path, then the next shortest path etc.

It is shortest_simple_paths.

So for example:

import networkx as nx
G = nx.Graph()
G.add_edges_from([[0,1], [1,2], [2,3], [0,2], [0,3]])
X = nx.shortest_simple_paths(G, 0, 3) #generator to find paths from 0 to 3 in order from shortest to longest.
for x in X:
    print(x)
> [0, 3]
> [0, 2, 3]
> [0, 1, 2, 3]
#note that X is now empty because it is a generator
for x in X:
    print(x) #nothing to see here
> 
#if you just want the first two:
X = nx.shortest_simple_paths(G, 0, 3)
for k in range(2):
    print(next(X))
> [0, 3]
> [0, 2, 3]

This algorithm will find all paths, but it is set up so that it only does the additional work to calculate the k'th shortest path when it is asked for it and then it forgets it. See Understanding generators in Python for more on generators.

Joel
  • 22,598
  • 6
  • 69
  • 93