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:

optimise length      : 4,461 m,  7.97 min
optimise travel_time : 4,687 m,  6.20 min

The shorter route takes 28% longer. Going 226 m further saves 106 seconds, 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, -2.2426, 53.4808)
destination = ox.nearest_nodes(G, -2.2300, 53.4880)

# 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")

53 nodes, 4,687 m, 6.20 min

Step-by-step solution #

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,461 m,  7.97 min, 63 nodes
  optimise travel_time :   4,687 m,  6.20 min, 53 nodes

Five percent further, 22% quicker. On many pairs in a dense urban network the two routes coincide exactly; this is the pair, out of 300 random ones, where they diverged most. On a trip with a motorway option the gap can be far larger — twice the distance in half the time.

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: 5,019 m over 38 nodes

Thirteen percent longer than the length-optimal route, over 25 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': 4324521, 'highway': 'primary', 'length': 59.6, ...}}

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, 412 vertices

The 412 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 #

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")

route 4,687 m ± 102 m of snapping error

Both endpoints were moved to reach a junction, and both offsets are unmeasured parts of the real journey. On a 4.7 km drive, 102 m is noise. On a 400 m walk it would be 25%. See how to snap points to a street network.

Code examples #

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", Gp=None):
    """Route between two coordinates, returning geometry and both cost measures."""
    Gp = Gp if Gp is not None else ox.project_graph(G)

    origin, o_snap = ox.nearest_nodes(Gp, origin_xy[0], origin_xy[1], return_dist=True)
    dest, d_snap = ox.nearest_nodes(Gp, 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, (-2.2426, 53.4808), (-2.2300, 53.4880), weight=weight)

  length     : 4,461 m, 7.97 min, 63 nodes (± 102 m snapping)
  travel_time: 4,687 m, 6.20 min, 53 nodes (± 102 m snapping)

Reporting both costs regardless of which was optimised is what lets a reader see the trade. A function that returns only the optimised cost hides the fact 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


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     : 5,479 m, 84 m of climb
  cycle_cost : 6,102 m, 41 m of climb

Eleven percent further for half the climbing. The penalty_per_metre_climb is a modelling choice — 8 means "a metre up is worth eight metres flat" — and it decides the answer, so it belongs in the output rather than buried 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      4687      6.20     53   +0.0%
    2      4663      6.21     43   +0.2%
    3      4709      6.22     54   +0.3%

Three routes within 0.3% of each other on time, spanning 46 m in distance. Notice that rank 2 is the shortest of the three by distance and uses ten fewer nodes — it is ranked second because the ranking is by travel time, and it loses by 0.6 of a second.

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 the alternatives differ by half a second, presenting one as optimal overstates the precision of the underlying speed estimates enormously.

Explanation #

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 — 5,019 m against 4,461 m in the measurement above, 13% longer over 25 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,461 m / 7.97 min against 4,687 m / 6.20 min — is 5% in distance and 22% 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.

Edge cases or notes #

• Always pass weight. Without it you minimise junction count, which was 25% 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 — 13% 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 — it was 102 m across both ends here.