Shortest route between points in a city – with Python and OpenStreetMap

After the article for introduction to Graphs in Python, I have decided to put the graph theory into practice and start looking for the shortest points between points in a city. Parts of the code are inspired from the book Optimization Algorithms by Alaa Khamis, other parts are mine 🙂

The solution uses several powerful Python libraries:

• OSMnx to download and work with real road networks from OpenStreetMap
• NetworkX to model the road system as a graph and calculate the shortest path using Dijkstra’s algorithm
• Folium for interactive map visualization

We start by geocoding the two landmarks to get their latitude and longitude. Then we build a drivable street network centered around the Levski Monument using ox.graph_from_address. After snapping both points to the nearest graph nodes, we compute the shortest route by distance. Finally, we visualize everything both in an interactive map and in a clean black-on-white static graph where the path is drawn in yellow.

import shutup
shutup.please()

import pandas as pd
import matplotlib.pyplot as plt
import numpy as np

import networkx as nx
import osmnx as ox
import folium

type_of_network = 'drive'
start_point_name = "Monument Vasil Levski, Sofia, Bulgaria"
end_point_name = "Sveti Sedmochislenitsi Church, Sofia, Bulgaria"
start_point_geocode = ox.geocode(start_point_name)
end_point_geocode = ox.geocode(end_point_name)

center_point = (
        (start_point_geocode[0]+end_point_geocode[0]) /2,
        (start_point_geocode[1]+end_point_geocode[1])/2
)
graph = ox.graph_from_point(center_point, dist=1000, network_type=type_of_network)
ox.plot_graph(
    graph,
    bgcolor = 'yellow',
    edge_color = 'black',
    node_color = 'black',
    edge_linewidth=1,
    node_size = 50,
    figsize=(10,10)
)

origin_node = ox.distance.nearest_nodes(graph, start_point_geocode[1],start_point_geocode[0])
destination_node = ox.distance.nearest_nodes(graph, end_point_geocode[1],end_point_geocode[0])

fig, ax = ox.plot_graph(
    graph,
    bgcolor = 'black',
    edge_color = 'white',
    node_color = 'white',
    edge_linewidth=1,
    node_size = 50,
    show = False,
    close= False
)

origin_xy = (graph.nodes[origin_node]['x'],graph.nodes[origin_node]['y'])
destination_xy = (graph.nodes[destination_node]['x'],graph.nodes[destination_node]['y'])

ax.scatter(*origin_xy, s=80, c="red", label = "Origin", zorder = 3)
ax.scatter(*destination_xy, s=80, c="green", label = "Destination", zorder = 3)

ax.legend(facecolor = "white")
plt.title("Graph with Origin (red) and Destination (green) nodes")
plt.show()

route = nx.shortest_path(graph, origin_node, destination_node, weight = 'length', method = 'dijkstra')
route_length_meters = nx.shortest_path_length(graph, origin_node, destination_node, weight ='length', method = 'dijkstra')
ox.plot_graph_route(graph, route)

The full code is implemented in a Jupyter Notebook in GitHub and explained in the video.

GitHub link: https://github.com/Vitosh/Python_personal/tree/master/YouTube/037_Python-shortest-route-between-points

Enjoy the rest of your day! 🙂