CODEWITHSUNDEEP
pythonshortest-pathosmnx
RB10
RB10

Reputation: 53

Underlying algorithm used by OSMNx package to find shortest route?

The shortest_path function from the NetworkX library to get the optimal path which minimizes the total length uses Dijkstra's algorithm by default.

route = nx.shortest_path(G, origin_node, destination_node, weight = 'length')

What is the algorithm used by the OSMNx function to find the shortest path?

route = ox.shortest_path(G, orig, dest, weight="length")

Does the function also use the Dijkstra algorithm?

Upvotes: 1

Views: 217

Answers (1)

swiss_knight
swiss_knight

Reputation: 7781

The ox.shortest_path function relies on the NetworkX shortest_path one as you can see in the osmnx source code:

https://github.com/gboeing/osmnx/blob/66775dbb723ab8c605ff8a8eb061647147c25381/osmnx/_api.py#L9

-> https://github.com/gboeing/osmnx/blob/c034e2bf670bd8e9e46c5605bc989a7d916d58f3/osmnx/distance.py#L377-L442

--> https://github.com/gboeing/osmnx/blob/c034e2bf670bd8e9e46c5605bc989a7d916d58f3/osmnx/distance.py#L370-L374

def _single_shortest_path(G, orig, dest, weight):
    (...)
    return nx.shortest_path(G, orig, dest, weight=weight)

def shortest_path(G, orig, dest, weight="length", cpus=1):
    (....)
    paths = [_single_shortest_path(G, o, d, weight) for o, d in zip(orig, dest)]

Links between functions in this code summary:

enter image description here

So yes, it's Dijkstra

Upvotes: 1

Related Questions