CODEWITHSUNDEEP
python-3.xnetworkxosmnx
Salil Sharma
Salil Sharma

Reputation: 79

K-shortest paths using networkx package in python

I have created a multidigraph of motorway of Netherlands using osmnx package. Motorway network of the Netherlands

The graph is a multidigraph returned from osmnx. Since I am interested to compute k-shortest paths between an origin and a destination, I tried networkx library. However, networkx does not seem to work with multidigraph. All I can compute the shortest path.

I would like to ask if there is any other way to perform the k-shortest path computation in python over multidigraph.

Upvotes: 1

Views: 5605

Answers (2)

Yonas Kassa
Yonas Kassa

Reputation: 3690

Now, osmnx has k_shortest_paths method implemented for multidigraph, you can use it as follows.

ox.routing.k_shortest_paths(G, s, t, k)

Upvotes: 2

Joel
Joel

Reputation: 23827

Try using the networkx command shortest_simple_paths (documentation).

It returns a generator which returns one path at a time from shortest to longest.

G = nx.karate_club_graph()
X = nx.shortest_simple_paths(G, 0, 5)
k = 5
for counter, path in enumerate(X):
     print(path)
     if counter == k-1:
         break
> [0, 5]
> [0, 6, 5]
> [0, 10, 5]
> [0, 6, 16, 5]
> [0, 4, 6, 5]

This will work with DiGraphs, but I'm not sure about a MultiDiGraph. It's not clear to me that a road network would be a MultiDiGraph, however.

Upvotes: 2

Related Questions