How to Calculate the Shortest Path Along a Street Network

Problem statement

You have a graph and two points, and you want the route between them. The call is one line:

route = nx.shortest_path(G, origin, destination, weight="length")

Three things then go wrong, in increasing order of subtlety.

It raises NetworkXNoPath for a pair a few streets apart. It returns a route and you cannot get its length back out, because the graph is a multigraph and G[u][v]["length"] is a KeyError. And when it does work, "shortest" turns out to be a choice. Step 2 routes one pair of points in central Manchester both ways:

optimise length      : 4,061 m,  8.19 min
optimise travel_time : 4,155 m,  5.25 min

The shorter route takes 56% longer. Going 94 m further saves almost 3 minutes, because the longer route uses faster roads. Neither is the shortest path; each is the shortest path under a different definition of cost.

Quick answer

import networkx as nx
import osmnx as ox

# 1. a strongly connected graph, so NoPath is structurally impossible
G = G.subgraph(max(nx.strongly_connected_components(G), key=len)).copy()
G = ox.add_edge_travel_times(ox.add_edge_speeds(G))

# 2. snap the endpoints
origin = ox.nearest_nodes(G, *ORIGIN)                   # (lon, lat)
destination = ox.nearest_nodes(G, *DESTINATION)

# 3. route, and measure both costs
route = nx.shortest_path(G, origin, destination, weight="travel_time")
metres = sum(G[u][v][0]["length"] for u, v in zip(route[:-1], route[1:]))
seconds = sum(G[u][v][0]["travel_time"] for u, v in zip(route[:-1], route[1:]))

print(f"{len(route)} nodes, {metres:,.0f} m, {seconds / 60:.2f} min")

67 nodes, 4,155 m, 5.25 min

A strongly connected graph, a chosen weight, geometry

1. Make NetworkXNoPath structurally impossible

largest = max(nx.strongly_connected_components(G), key=len)
G = G.subgraph(largest).copy()
assert nx.is_strongly_connected(G)

Inside a strongly connected graph every pair of nodes has a path by definition. That converts a runtime exception into a build-time guarantee, and it is the single most useful thing you can do before routing — see no path exists between two nodes.

.copy() is required because subgraph() returns a read-only view.

2. Choose the weight deliberately

for weight in ("length", "travel_time"):
    route = nx.shortest_path(G, origin, destination, weight=weight)
    metres = sum(G[u][v][0]["length"] for u, v in zip(route[:-1], route[1:]))
    seconds = sum(G[u][v][0]["travel_time"] for u, v in zip(route[:-1], route[1:]))
    print(f"  optimise {weight:12}: {metres:7,.0f} m, {seconds / 60:5.2f} min, "
          f"{len(route)} nodes")

  optimise length      :   4,061 m,  8.19 min, 58 nodes
  optimise travel_time :   4,155 m,  5.25 min, 67 nodes

Two percent further, 36% quicker. On many pairs in a dense urban network the two routes coincide exactly — a first draft of this page picked a pair 1.3 km apart and got the same 23-node route both ways — so the setup picks, out of 300 random pairs, the one where they diverge most. On a trip with a motorway option the gap can be far larger.

Never omit weight. Without it, shortest_path minimises the number of edges, which is a route with the fewest junctions and no relation to distance or time.

hops = nx.shortest_path(G, origin, destination)          # weight=None
metres = sum(G[u][v][0]["length"] for u, v in zip(hops[:-1], hops[1:]))
print(f"  fewest edges: {metres:,.0f} m over {len(hops)} nodes")

  fewest edges: 4,437 m over 45 nodes

Nine percent longer than the length-optimal route, over 13 fewer nodes — it takes long arterial roads to save junctions, which is what minimising edge count means.

3. Get the cost out correctly

The graph is a multigraph, so G[u][v] is a dict of parallel edges keyed by integer:

print(G[origin][next(iter(G[origin]))])

{0: {'osmid': 27948417, 'highway': 'residential', 'name': 'London Street', 'oneway': False, 'reversed': False, 'length': np.float64(26.068274036942853), 'speed_kph': 34.3727583640553, 'travel_time': 2.730237286720982}}

G[u][v]["length"] raises KeyError: 'length'. Two correct forms:

# the first parallel edge — fine when you know there is only one
metres = sum(G[u][v][0]["length"] for u, v in zip(route[:-1], route[1:]))

# the cheapest parallel edge — correct in general
metres = sum(min(d["length"] for d in G[u][v].values())
             for u, v in zip(route[:-1], route[1:]))

Or let NetworkX do it, which is exact and avoids the question entirely:

metres = nx.shortest_path_length(G, origin, destination, weight="length")

Note that shortest_path_length with weight="length" gives the length of the length-optimal route. If you routed on travel_time, summing the edges of that route is the only way to get its length.

4. Turn the route into geometry

import geopandas as gpd
from shapely.ops import linemerge

edges = ox.graph_to_gdfs(G, nodes=False)
pairs = list(zip(route[:-1], route[1:]))
segments = edges.loc[[(u, v, 0) for u, v in pairs], "geometry"]

line = linemerge(list(segments))
print(f"{line.geom_type}, {len(line.coords) if line.geom_type == 'LineString' else '—'} vertices")

LineString, 260 vertices

The 260 vertices come from the edge geometries — the curve of each street, which simplification folded into the edges. ox.plot_graph_route(G, route) does this for a quick look; the explicit version is what you write to a file.

If linemerge returns a MultiLineString, the segments do not connect end-to-end — usually because a key other than 0 was the actual routed edge.

5. Handle the endpoints honestly

from pyproj import Transformer

Gp = ox.project_graph(G)
to_graph = Transformer.from_crs("EPSG:4326", Gp.graph["crs"], always_xy=True)
x1, y1 = to_graph.transform(*ORIGIN)
x2, y2 = to_graph.transform(*DESTINATION)
origin, origin_snap = ox.nearest_nodes(Gp, x1, y1, return_dist=True)
destination, dest_snap = ox.nearest_nodes(Gp, x2, y2, return_dist=True)

print(f"route {metres:,.0f} m ± {origin_snap + dest_snap:.0f} m of snapping error")

town_hall = to_graph.transform(-2.2444, 53.4793)          # Albert Square: an address, not a junction
node, snap = ox.nearest_nodes(Gp, *town_hall, return_dist=True)
print(f"Manchester Town Hall snaps {snap:.0f} m to node {node}")

route 4,061 m ± 0 m of snapping error
Manchester Town Hall snaps 62 m to node 3356277

This pair was chosen from the graph's own nodes, so neither end moved. Real endpoints are addresses, and an address is rarely a junction: the Town Hall snaps 62 m. Both offsets are unmeasured parts of the real journey — on a 4 km drive, a few tens of metres at each end is noise; on a 400 m walk, 62 m is 15%. See how to snap points to a street network.

Both costs, a custom cost and k alternatives

The data used on this page

OSM's drive network around Manchester Town Hall, and Copernicus DEM heights for Example 2. Overpass via the maps.mail.ru mirror, as saved on 9 October 2026.

import io
import networkx as nx
import numpy as np
import os
import osmnx as ox
import rasterio
import requests
import zipfile

# OpenStreetMap as Overpass returned it on 9 October 2026, saved as osmnx's own cache so the counts
# below do not drift as OSM is edited; delete the cache folder to query live instead
if not os.path.exists("cache"):
    reply = requests.get("https://data.spatialworkflow.io/osm-cache-shortest-path-street-network-python-2026-10-09.zip", timeout=300)
    reply.raise_for_status()
    with zipfile.ZipFile(io.BytesIO(reply.content)) as archive:
        archive.extractall("cache")

ox.settings.overpass_url = "https://maps.mail.ru/osm/tools/overpass/api"
ox.settings.overpass_rate_limit = False
ox.settings.http_user_agent = "spatialworkflow.io guide examples (https://www.spatialworkflow.io/)"
G = ox.graph_from_point((53.4808, -2.2426), dist=2500, network_type="drive")

DEM = ("https://copernicus-dem-30m.s3.amazonaws.com/Copernicus_DSM_COG_10_N53_00_W003_00_DEM/"
       "Copernicus_DSM_COG_10_N53_00_W003_00_DEM.tif")
with rasterio.open(DEM) as src:
    xy = [(data["x"], data["y"]) for _, data in G.nodes(data=True)]
    heights = dict(zip(G.nodes, (float(v[0]) for v in src.sample(xy))))


def elevation_at(node):
    return heights[node]


# the pair used on this page: of 300 random node pairs, the one where optimising
# time instead of length changes the route most
Gs = ox.add_edge_travel_times(ox.add_edge_speeds(
    G.subgraph(max(nx.strongly_connected_components(G), key=len)).copy()))
rng = np.random.default_rng(0)
nodes = list(Gs.nodes)


def cost(route, attr):
    return sum(min(d[attr] for d in Gs[u][v].values()) for u, v in zip(route[:-1], route[1:]))


best = None
for a, b in rng.choice(nodes, size=(300, 2)):
    by_length = nx.shortest_path(Gs, a, b, weight="length")
    by_time = nx.shortest_path(Gs, a, b, weight="travel_time")
    saving = cost(by_length, "travel_time") / cost(by_time, "travel_time")
    if best is None or saving > best[0]:
        best = (saving, a, b)
ORIGIN = (Gs.nodes[best[1]]["x"], Gs.nodes[best[1]]["y"])
DESTINATION = (Gs.nodes[best[2]]["x"], Gs.nodes[best[2]]["y"])
print(f"{len(G.nodes):,} nodes; node heights {min(heights.values()):.0f}–{max(heights.values()):.0f} m")
print(f"pair: {ORIGIN[1]:.4f}, {ORIGIN[0]:.4f} to {DESTINATION[1]:.4f}, {DESTINATION[0]:.4f}")

5,018 nodes; node heights 22–75 m
pair: 53.4946, -2.2783 to 53.4765, -2.2606

Example 1 — a routing function that reports both costs

import networkx as nx
import numpy as np
import osmnx as ox
from shapely.ops import linemerge


def route_between(G, origin_xy, destination_xy, *, weight="travel_time"):
    """Route between two coordinates, returning geometry and both cost measures."""

    # lon/lat against the unprojected graph: OSMnx measures great-circle metres
    origin, o_snap = ox.nearest_nodes(G, origin_xy[0], origin_xy[1], return_dist=True)
    dest, d_snap = ox.nearest_nodes(G, destination_xy[0], destination_xy[1],
                                    return_dist=True)

    if origin == dest:
        return {"nodes": [origin], "length_m": 0.0, "time_s": 0.0,
                "snap_m": o_snap + d_snap, "geometry": None}

    route = nx.shortest_path(G, origin, dest, weight=weight)
    pairs = list(zip(route[:-1], route[1:]))

    def edge_cost(u, v, attr):
        return min(d[attr] for d in G[u][v].values())

    length_m = sum(edge_cost(u, v, "length") for u, v in pairs)
    time_s = sum(edge_cost(u, v, "travel_time") for u, v in pairs)

    geoms = []
    for u, v in pairs:
        data = min(G[u][v].values(), key=lambda d: d[weight])
        if "geometry" in data:
            geoms.append(data["geometry"])
    geometry = linemerge(geoms) if geoms else None

    result = {
        "nodes": route,
        "n_nodes": len(route),
        "length_m": round(length_m, 1),
        "time_s": round(time_s, 1),
        "time_min": round(time_s / 60, 2),
        "snap_m": round(o_snap + d_snap, 1),
        "weight": weight,
        "geometry": geometry,
    }
    print(f"  {weight:11}: {result['length_m']:,.0f} m, {result['time_min']:.2f} min, "
          f"{result['n_nodes']} nodes (± {result['snap_m']:.0f} m snapping)")
    return result


for weight in ("length", "travel_time"):
    route_between(G, ORIGIN, DESTINATION, weight=weight)

  length     : 4,061 m, 8.19 min, 58 nodes (± 0 m snapping)
  travel_time: 4,155 m, 5.25 min, 67 nodes (± 0 m snapping)

Reporting both costs, whichever was optimised, shows the trade; returning only the optimised one hides that a choice was made.

Using min(...) over parallel edges rather than [0] is the generally correct form — with a dual carriageway, edge 0 may not be the one the router used.

Example 2 — a custom cost that avoids something

def add_hill_penalty(G, dem_lookup, *, penalty_per_metre_climb=8.0):
    """A cost that treats a metre of climb as several metres of flat riding."""
    for u, v, key, data in G.edges(keys=True, data=True):
        rise = max(0.0, dem_lookup(v) - dem_lookup(u))
        data["cycle_cost"] = data["length"] + rise * penalty_per_metre_climb
    return G


dest = destination
G = add_hill_penalty(G, elevation_at)

for weight in ("length", "cycle_cost"):
    route = nx.shortest_path(G, origin, dest, weight=weight)
    pairs = list(zip(route[:-1], route[1:]))
    metres = sum(min(d["length"] for d in G[u][v].values()) for u, v in pairs)
    climb = sum(max(0.0, elevation_at(v) - elevation_at(u)) for u, v in pairs)
    print(f"  {weight:11}: {metres:,.0f} m, {climb:.0f} m of climb")

  length     : 4,061 m, 32 m of climb
  cycle_cost : 4,061 m, 32 m of climb

Here the penalty changes nothing: both weights take the same 4,061 m route with 32 m of climb, because central Manchester is flat (nodes 22–75 m) and no detour saves enough climbing to pay for its length. On hilly ground the same weight moves routes a long way. penalty_per_metre_climb — 8 means "a metre up is worth eight metres flat" — decides the answer, so it belongs in the output, not in a default.

Note the asymmetry: rise is computed per directed edge, so the uphill direction is penalised and the downhill one is not. That is correct, and it is only possible because the graph is directed.

Example 3 — k shortest paths, for alternatives

from itertools import islice


def k_routes(G, origin, dest, k=3, weight="travel_time"):
    paths = ox.k_shortest_paths(G, origin, dest, k, weight=weight)
    rows = []
    for i, route in enumerate(islice(paths, k), 1):
        pairs = list(zip(route[:-1], route[1:]))
        metres = sum(min(d["length"] for d in G[u][v].values()) for u, v in pairs)
        seconds = sum(min(d["travel_time"] for d in G[u][v].values()) for u, v in pairs)
        rows.append({"rank": i, "length_m": round(metres), "time_min": round(seconds / 60, 2),
                     "nodes": len(route)})
    import pandas as pd
    frame = pd.DataFrame(rows)
    frame["vs_best"] = (frame["time_min"] / frame["time_min"].iloc[0] - 1).map("{:+.1%}".format)
    print(frame.to_string(index=False))
    return frame


k_routes(G, origin, dest, k=3)

 rank  length_m  time_min  nodes vs_best
    1      4155      5.25     67   +0.0%
    2      4161      5.25     67   +0.0%
    3      4173      5.27     68   +0.4%

Three routes within 0.4% of each other on time — about a second between first and third — and 18 m apart in distance.

That is the useful output of a k-shortest-paths query: not "here is the answer" but "here are several near-equivalent answers, and the ranking depends on which cost you asked for". Where alternatives differ by a second, calling one optimal overstates the precision of the speed estimates.

Unweighted search, length against time, A*

Why omitting weight is so wrong

nx.shortest_path without a weight runs breadth-first search and minimises the number of edges. On a street network an edge is a block, so it minimises junctions.

That produces a route that takes long arterial roads to avoid turnings — 4,437 m against 4,061 m in the measurement above, 9% longer over 13 fewer nodes. It is not an approximation of the shortest route; it optimises something nobody wants.

The mistake survives because the result looks like a route and no exception is raised. Pass weight explicitly, every time.

Why length and time disagree

Dijkstra minimises the sum of edge weights, and length and travel_time order the edges differently. A 200 m stretch of 50 kph road costs more length and less time than a 150 m stretch at 20 kph.

The measured gap here — 4,061 m / 8.19 min against 4,155 m / 5.25 min — is 2% in distance and 36% in time on a uniformly urban network. Add a motorway and the routes diverge completely: three times the distance in half the time is normal for an intercity trip.

Choose from the question. Walking and cycling distance thresholds want length; drive-time catchments and emergency response want travel_time. Both are "shortest path"; neither is "the" shortest path.

Why the multigraph keeps catching people

Two nodes can be joined by more than one edge — a dual carriageway, a road plus a service road, a junction with a slip road. NetworkX represents that with a third index, the key.

So G[u][v] is {0: {...}, 1: {...}}, and G[u][v]["length"] looks up the key "length" among the integers 0 and 1. Hence KeyError: 'length' on a graph that obviously has lengths.

G[u][v][0] works whenever there is only one parallel edge, which is most of the time — and fails silently by picking the wrong one when there are two. min(d[attr] for d in G[u][v].values()) is the form that is always right.

Why A* is worth knowing about

Dijkstra explores outward in all directions until it settles the destination. A* uses a heuristic — a lower bound on the remaining cost — to explore preferentially toward the target.

For a single route on a city graph the difference is small; for repeated queries on a large network it is substantial:

def straight_line(a, b):
    return np.hypot(Gp.nodes[a]["x"] - Gp.nodes[b]["x"],
                    Gp.nodes[a]["y"] - Gp.nodes[b]["y"])

route = nx.astar_path(G, origin, dest, heuristic=straight_line, weight="length")

The heuristic must never overestimate the remaining cost, or the result is not optimal. Straight-line distance is a valid heuristic for length because a route can never be shorter than the crow flies. For travel_time you would need straight-line distance divided by the network's maximum speed — and getting that wrong produces plausible, suboptimal routes with no error.

Multigraph access, endpoint snapping and turn restrictions

• Always pass weight. Without it you minimise junction count, which was 9% longer here.
• G[u][v]["length"] raises on a multigraph. Use [0], or min() over the parallel edges.
• shortest_path_length with a different weight gives the cost of a different route. Sum the edges of the route you actually took.
• Route on the unprojected graph — length is already metres. Project only for snapping and geometry.
• A needs an admissible heuristic.* Straight-line distance works for length; for travel_time divide by the maximum speed.
• Snapping error applies at both ends and is unmeasured. Report it alongside the route length.
• linemerge returning a MultiLineString means the segments do not connect — usually a parallel-edge key mismatch.
• Turn restrictions are not modelled. OSMnx graphs ignore no-left-turn and similar, so routes can be slightly optimistic.

Internal links

• Street networks as graphs explained — why it is a directed multigraph
• NetworkX says no path exists between two nodes — the exception and how to prevent it
• Street network routing returns absurd distances — when the route is wrong rather than missing
• How to build a street network graph in Python with OSMnx — producing a routable graph
• How to snap points to a street network in Python — the endpoints
• How to measure network distance for many origin-destination pairs — routing at scale
• Network distance vs straight-line distance explained — why bother with any of this
• How to generate isochrones in Python — the same traversal, a different output

FAQ

Why does my route ignore distance entirely?

You omitted weight, so NetworkX minimised the number of edges. That produces a route with the fewest junctions — 9% longer than necessary in the example here.

Should I optimise on length or travel time?

Length for walking, cycling and distance thresholds. Travel time for driving, catchments and anything phrased in minutes. They give different routes.

Why does G[u][v]["length"] raise a KeyError?

It is a multigraph, so G[u][v] is a dict keyed by edge number. Use G[u][v][0]["length"], or take the minimum across the parallel edges.

How do I get the length of a route I optimised on time?

Sum the length attribute along that route's edges. shortest_path_length(weight="length") would give you the length of a different, length-optimal route.

Should I use A* instead of Dijkstra?

For many repeated queries on a large graph, yes. The heuristic must never overestimate the remaining cost — straight-line distance is valid for length, but for travel_time you must divide it by the maximum speed.

Are the travel times accurate?

They come from imputed speeds and ignore congestion, turn delays and traffic lights. Good for comparing routes, weak for predicting an absolute journey time.

Why does the route not start exactly at my point?

Because it starts at the nearest graph node. Report the snap distance alongside the route — the Town Hall alone moved 62 m here.