The world’s leading publication for data science, AI, and ML professionals.

Shortest Path (Dijkstra’s) algorithm step-by-step Python guide

An update using OSMNX 1.6 and a long-distance path

Image by the Author. The resultant shortest path (~350km) in Morocco
Image by the Author. The resultant shortest path (~350km) in Morocco

This well-known algorithm is implemented in the Python library OSMNX and can be used to find the shortest path weighted by distance or time between two locations. The algorithm uses the OpenStreetMap (OSM) network to either drive, walk, or bike, to find the route using the Python library NETWORKX in the background.

I am writing this update because the parameters of the functions have changed a little bit and I have been asked why my code is not working in old blog posts, and it is simply because the code was written with older versions of osmnx.

The old tutorial contains quite valuable processes, but I also decided to do a step-by-step guide so the process of getting the shortest path is more precise and the analyst that uses this guide can really get the idea of the process.

Here are the old tutorials if you want to give it a look.

In Helsinki (Finland), using a different networks

The shortest path algorithm used in the OSM street network

In Tartu (Estonia), using a walking network

Shortest path algorithm with OSM walking network

OSM data license

Introduction

In this practice, I am going to use two locations from Morocco. The practice was suggested by one of my readers Hanae who provided the origin and destination.

Image by the Author. Origin and destination locations.
Image by the Author. Origin and destination locations.

Coding practice

As I mentioned, I am going to do a step-by-step guide so let’s start. Beforehand let’s import the needed libraries

import osmnx as ox
import geopandas as gpd
from shapely.geometry import Point, LineString
import pandas as pd
import matplotlib.pyplot as plt

1. Define origin and destination

Simply, we are going to create geometry objects as Points:

# origin and destination geom

origin_geom = Point(-5.6613932957355715, 32.93210288339607)

destination_geom = Point(-3.3500597061072726, 34.23038027794419)

2. Fetch the OSM Graph object

Then, we will extract the graph that we are going to use for generating the Shortest Path. Let’s see step by step.

  • Create GeoDataFrames from the origin and destination
# create origin dataframe
origin =  gpd.GeoDataFrame(columns = ['name', 'geometry'], crs = 4326, geometry = 'geometry')
origin.at[0, 'name'] = 'origin'
origin.at[0, 'geometry'] =origin_geom

# create destination dataframe
destination =  gpd.GeoDataFrame(columns = ['name', 'geometry'], crs = 4326, geometry = 'geometry')
destination.at[0, 'name'] = 'destination'
destination.at[0, 'geometry'] = destination_geom
  • Get the Graph that contains the origin and destination

We will use the function envelope from Geopandas to use the polygon as a mask to fetch the Graph.

A simple function first.

def get_graph_from_locations(origin, destination, network='drive'):
    '''
    network_type as drive, walk, bike
    origin gdf 4326
    destination gdf 4326
    '''
    # combine and area buffer
    combined = pd.concat([origin, destination])

    convex = combined.unary_union.envelope # using envelope instead of convex, otherwise it breaks the unary_union

    graph_extent = convex.buffer(0.02)

    graph = ox.graph_from_polygon(graph_extent, network_type= network)

    return graph

Then, use it and plot the result.

graph = get_graph_from_locations(origin, destination)
fig, ax = ox.plot_graph(graph, node_size=0, edge_linewidth=0.2)
Image by the Author. Graph the contains origin and destination
Image by the Author. Graph the contains origin and destination

3. Find the closest nodes of origin and destination

Get the closest nodes that are part of the network using the origin and destination locations. The node’s code can be obtained using the osmnx functions.

# ------------- get closest nodes

# origin
closest_origin_node = ox.nearest_nodes(G=graph, 
                                       X=origin_geom.x, 
                                       Y=origin_geom.y)

# destination
closest_destination_node = ox.nearest_nodes(G=graph, 
                                           X=destination_geom.x, 
                                           Y=destination_geom.y)

You can check and notice that we only have codes at the moment.

4. Find the Shortest Path

Then, use the shortest path functions to obtain the route.

# run
route = ox.shortest_path(graph, 
                         orig = closest_origin_node, 
                         dest = closest_destination_node, 
                         weight = 'length')

This will give back a bunch of node’s code that are part of the route.

Image by the AuthorNode's codes
Image by the AuthorNode’s codes

5. Create a Line Geometry from nodes

We will extract the node’s geometries from the Graph and create a LineString geometry that represents the shortest path

First a function for this.

def nodes_to_route(graph_nodes, path_nodes):

    # Extract the route nodes of the graph
    route_nodes = graph_nodes.loc[path_nodes]

    # ---> note! If you have more routes, check for each one, to be removed in length is 1.  A path can not be built with only 1 node.

    # Create a LineString out of the route
    list_geom = route_nodes.geometry.to_list()
    path = LineString(list_geom)

    # Append the result into the GeoDataFrame
    route_df = gpd.GeoDataFrame( [[path]] )

    # Add a column name
    route_df.columns = ['geometry'] 

    # Set geometry
    route_df = route_df.set_geometry('geometry')

    # Set coordinate reference system
    route_df.crs = graph_nodes.crs

    # remove nans
    route_df = route_df.dropna(subset=['geometry'])

    return route_df

Get the nodes, and use them in the function.

# get all network nodes
graph_nodes = ox.graph_to_gdfs(graph, edges=False)

# get the line geometries from osm nodes
route_gdf = nodes_to_route(graph_nodes, route)

6. Compute distance

We are going to measure the route in meters with a Mercator projection. You can use the location projection if you want to have something more accurate.

First, a function for this.

def compute_distance(shortest_path_gdf):
    '''
    Compute distance in EPSG:3387

    '''

    # project WGS84 to EPSG3387
    distances = shortest_path_gdf.to_crs("EPSG:3387").geometry.length

    # add
    shortest_path_gdf['distance'] = distances

    return shortest_path_gdf

Then, use it:

# calculate distance m
route_distance_gdf = compute_distance(route_gdf)

It will measure the route with ~351.243 meters.

7. Save network and path

Save in your local disk the network and path for maps.

Fetch the network and define GeoDataFrame:

# fetch network
network = ox.graph_to_gdfs(graph, nodes=False)

# get only needed columns
network_gdf = network.reset_index(drop=True)[['geometry']]

Then store:

network_gdf.to_file(r'osm_network.gpkg')
route_distance_gdf.to_file(r'osm_shortest_path.gpkg')

You can use this data to create your own map. For example, this one in QGIS:

Image by the Author. Shortest path and network in QGIS
Image by the Author. Shortest path and network in QGIS

8. Plot results

We will check if we are doing our work right by plotting all elements.

# plot network
ax = network_gdf.plot(figsize=(12, 10), linewidth = 0.2, color='grey', zorder=0);

# origin and destination
origin.plot(ax=ax, markersize=46, alpha=0.8, color='blue', zorder=1)
destination.plot(ax=ax, markersize=46, alpha=0.8, color='green', zorder=2)

# route
route_distance_gdf.plot(ax=ax, linewidth = 3, color='red', alpha=0.4, zorder=3)

plt.axis(False);

The result will be as simple as this.

Image by the Author. Shortest path, network, origin, and destination in Matplotlib
Image by the Author. Shortest path, network, origin, and destination in Matplotlib

Known limitation

The shortest path is generated by the union of the nodes’ network and the line does not really match the road. That is totally OK because what we want is to have an approximation. If you are willing to do navigation you should use Google API for Routing, or any other provider.

Image by the Author. The line is created by nodes.
Image by the Author. The line is created by nodes.

Conclusion

The shortest path algorithm using OSMNX gives an approximation of the route and can be used broadly for accessibility studies at urban or regional scales. The Python library is constantly updated and it is possible that the functions or parameters change so it is recommended to continuously update the library versions in our workflows.

If you want to reach me for questions or customized analysis:

Bryan R. LinkedIn


Related Articles