NetworkX Says No Path Exists Between Two Nodes

Problem statement

Two addresses a few streets apart, and routing fails:

try:
    route = nx.shortest_path(G, origin, destination, weight="length")
except nx.NetworkXNoPath as exc:
    print(f"{type(exc).__name__}: {exc}")
print(f"{len(G.nodes):,} nodes; origin in G: {origin in G}, destination in G: {destination in G}; "
      f"{ox.distance.great_circle(G.nodes[origin]['y'], G.nodes[origin]['x'], G.nodes[destination]['y'], G.nodes[destination]['x']):.0f} m apart")

NetworkXNoPath: No path between 4841438 and 4830040.
5,018 nodes; origin in G: True, destination in G: True; 309 m apart

You can see both streets on a map, a few hundred metres apart. The graph has both nodes in it.

The exception is telling the truth: in the graph as loaded, there is no sequence of directed edges from one to the other. That is almost never because the streets are missing — it is because the graph is not strongly connected, and the standard connectivity check does not detect it.

Quick answer

import networkx as nx

print(f"weakly connected components:   {nx.number_weakly_connected_components(G)}")
print(f"strongly connected components: {nx.number_strongly_connected_components(G)}")

largest = max(nx.strongly_connected_components(G), key=len)
print(f"origin in largest SCC:      {origin in largest}")
print(f"destination in largest SCC: {destination in largest}")
print(f"out-degree of origin: {G.out_degree(origin)}, "
      f"in-degree of destination: {G.in_degree(destination)}")

weakly connected components:   1
strongly connected components: 28
origin in largest SCC:      False
destination in largest SCC: True
out-degree of origin: 0, in-degree of destination: 3

The origin has no outgoing edges. It is a node you can drive to and not from — a cul-de-sac reached by a one-way street, or a street severed by the download boundary.

Node id or connectivity, has_path, restrict, buffer, re-snap

1. Confirm it is connectivity, not a bad node id

print(origin in G, destination in G)
print(f"out-degree {G.out_degree(origin)}, in-degree {G.in_degree(origin)}")
print(f"out-degree {G.out_degree(destination)}, in-degree {G.in_degree(destination)}")

True True
out-degree 0, in-degree 1
out-degree 3, in-degree 3

An out-degree of zero is conclusive: nothing leaves this node, so no route from it can exist regardless of the destination.

If both degrees are healthy, the problem is further along the path — the two nodes are in different strongly connected components with no directed route between them.

2. Use has_path, not a try/except

if not nx.has_path(G, origin, destination):
    print("no directed route exists")

no directed route exists

has_path runs a single traversal and returns a bool. It is far cheaper than catching NetworkXNoPath from a full Dijkstra, and in a loop over thousands of pairs the difference is substantial.

But checking per pair is treating the symptom. The cure is to make the failure impossible.

3. Restrict the graph to its largest strongly connected component

before = len(G.nodes)
largest = max(nx.strongly_connected_components(G), key=len)
G = G.subgraph(largest).copy()

print(f"dropped {before - len(G.nodes)} stranded nodes "
      f"({(before - len(G.nodes)) / before:.2%})")
assert nx.is_strongly_connected(G)

dropped 33 stranded nodes (0.66%)

Inside a strongly connected graph, every ordered pair of nodes has a path by definition. NetworkXNoPath becomes structurally impossible, and you can delete every try/except around your routing calls.

.copy() is required — subgraph() returns a read-only view and ox.add_edge_speeds on it will fail.

4. Grow the download, and see which stranded nodes stay

Some stranded nodes are made by the download boundary: a street that leaves the extract and comes back is cut, and a node whose only exit was that street becomes a trap. Grow the download around a fixed 2 km study area and count what is still stranded inside it:

for buffer in (0, 500, 1500):
    g = ox.graph_from_point(centre, dist=2000 + buffer, network_type="drive",
                            truncate_by_edge=True)
    comps = list(nx.strongly_connected_components(g))
    largest = max(comps, key=len)
    inner = [n for n in g.nodes
             if ox.distance.great_circle(centre[0], centre[1], g.nodes[n]["y"], g.nodes[n]["x"]) <= 2000]
    stranded_inner = sum(1 for n in inner if n not in largest)
    print(f"buffer {buffer:5} m: {len(g.nodes):6,} nodes, {len(comps):3} components, "
          f"{len(g.nodes) - len(largest):3} stranded, {stranded_inner:3} of them in the 2 km study area")

buffer     0 m:  3,387 nodes,  32 components,  36 stranded,  24 of them in the 2 km study area
buffer   500 m:  5,186 nodes,  42 components,  48 stranded,  22 of them in the 2 km study area
buffer  1500 m:  9,075 nodes,  43 components,  52 stranded,  22 of them in the 2 km study area

Growing the download by 1.5 km removes only two of the 24 stranded nodes inside the study area. The total rises with the download, because a bigger area has more streets and a longer rim, but the 22 in the middle of Manchester stay: they are real one-way traps, not artefacts. So buffer the download, and still restrict to the largest component.

5. Re-snap your endpoints afterwards

This is the step people miss. Restricting the graph removes nodes, and any endpoint that had already been snapped to a removed node now points at nothing:

# WRONG — snapped before restricting
origin = ox.nearest_nodes(Gp, x, y)
G = G.subgraph(largest).copy()
nx.shortest_path(G, origin, dest)      # NodeNotFound if origin was stranded

# RIGHT — restrict, then snap
G = G.subgraph(largest).copy()
Gp = ox.project_graph(G)
origin = ox.nearest_nodes(Gp, x, y)

Snapping to the restricted graph guarantees the endpoint is routable, at the cost of a slightly longer snap where the nearest node was a stranded one.

6. Check you are not simply on the wrong network

for mode in ("drive", "walk"):
    g = ox.graph_from_point(centre, dist=2500, network_type=mode)
    print(f"{mode:6}: {len(g.nodes):6,} nodes, "
          f"{nx.number_strongly_connected_components(g):3} components")

drive :  5,018 nodes,  28 components
walk  : 26,150 nodes,   1 components

If you are routing a pedestrian, the drive network is the wrong graph and always will be. Pedestrianised streets, alleys, footpaths and cut-throughs are not in it, and pedestrians are not bound by one-way restrictions.

The walk network has exactly one strongly connected component, which is why walking routes essentially never fail for connectivity reasons.

A failing pair diagnosed and a pipeline that cannot fail

The data used on this page

OpenStreetMap's drive network within 2.5 km of Manchester Town Hall, through OSMnx; G_full keeps an untouched copy. The failing pair is not hand-picked: the origin is the stranded node — out-degree zero — nearest the Town Hall, and the destination is the routable node nearest a point 300 m east of it. Example 2's 4,000 trips are random points in the graph's extent, seeded. Overpass via the maps.mail.ru mirror while overpass-api.de was refusing connections. The OpenStreetMap answers are read as the Overpass mirror gave them on 10 October 2026.

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

# OpenStreetMap as Overpass returned it on 10 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-no-path-between-nodes-networkx-2026-10-10.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/)"
centre = (53.4808, -2.2426)
G = ox.graph_from_point(centre, dist=2500, network_type="drive")
G_full = G.copy()

largest_scc = max(nx.strongly_connected_components(G), key=len)
dead_ends = [n for n in G.nodes if G.out_degree(n) == 0]
origin = min(dead_ends, key=lambda n: ox.distance.great_circle(centre[0], centre[1], G.nodes[n]["y"], G.nodes[n]["x"]))
east = (G.nodes[origin]["x"] + 300 / (111_320 * np.cos(np.radians(centre[0]))), G.nodes[origin]["y"])
destination = min(largest_scc, key=lambda n: (G.nodes[n]["x"] - east[0]) ** 2 + (G.nodes[n]["y"] - east[1]) ** 2)

Gp_full = ox.project_graph(G)
xs = [d["x"] for _, d in Gp_full.nodes(data=True)]
ys = [d["y"] for _, d in Gp_full.nodes(data=True)]
rng = np.random.default_rng(0)
pairs = [((rng.uniform(min(xs), max(xs)), rng.uniform(min(ys), max(ys))),
          (rng.uniform(min(xs), max(xs)), rng.uniform(min(ys), max(ys)))) for _ in range(4000)]
print(f"{len(dead_ends)} nodes with out-degree 0; origin {origin}, destination {destination}")

12 nodes with out-degree 0; origin 4841438, destination 4830040

Example 1 — a diagnostic for a specific failure

import networkx as nx
import osmnx as ox


def diagnose_no_path(G, origin, destination):
    """Explain why a specific pair cannot be routed."""
    findings = []

    for name, node in (("origin", origin), ("destination", destination)):
        if node not in G:
            findings.append(f"{name} {node} is not in the graph at all")
            return findings

    if not G.is_directed():
        findings.append("graph is undirected — this should not happen with a street network")
        return findings

    if G.out_degree(origin) == 0:
        findings.append(f"origin has out-degree 0 — you can arrive and never leave. "
                        f"A cul-de-sac on a one-way, or severed by the download boundary.")
    if G.in_degree(destination) == 0:
        findings.append(f"destination has in-degree 0 — you can leave and never arrive.")

    components = {frozenset(c) for c in nx.strongly_connected_components(G)}
    largest = max(components, key=len)
    o_comp = next(c for c in components if origin in c)
    d_comp = next(c for c in components if destination in c)

    if o_comp is not d_comp:
        findings.append(
            f"origin is in a component of {len(o_comp)} node(s), "
            f"destination in one of {len(d_comp)} "
            f"(largest is {len(largest)})"
        )
    if origin not in largest:
        findings.append(f"origin is NOT in the largest strongly connected component")
    if destination not in largest:
        findings.append(f"destination is NOT in the largest strongly connected component")

    if nx.has_path(G.to_undirected(), origin, destination):
        findings.append("an UNDIRECTED path exists — this is a one-way problem, "
                        "not a missing-street problem")

    print(f"  origin {origin}: out-degree {G.out_degree(origin)}, "
          f"in-degree {G.in_degree(origin)}")
    print(f"  destination {destination}: out-degree {G.out_degree(destination)}, "
          f"in-degree {G.in_degree(destination)}")
    for finding in findings:
        print(f"  ✗ {finding}")
    if not findings:
        print("  ✓ a path should exist — check the weight attribute")
    return findings


diagnose_no_path(G_full, origin, destination)

  origin 4841438: out-degree 0, in-degree 1
  destination 4830040: out-degree 3, in-degree 3
  ✗ origin has out-degree 0 — you can arrive and never leave. A cul-de-sac on a one-way, or severed by the download boundary.
  ✗ origin is in a component of 1 node(s), destination in one of 4985 (largest is 4985)
  ✗ origin is NOT in the largest strongly connected component
  ✗ an UNDIRECTED path exists — this is a one-way problem, not a missing-street problem

The last line is the one that saves time. An undirected path existing proves the streets are present and the failure is about direction — so no amount of re-downloading will help.

Example 2 — a pipeline that cannot produce the exception

def routable(G):
    """Restrict to the largest strongly connected component, once, at load time."""
    components = sorted(nx.strongly_connected_components(G), key=len, reverse=True)
    largest = components[0]
    share = len(largest) / len(G.nodes)

    if share < 0.9:
        raise RuntimeError(
            f"largest strongly connected component holds only {share:.1%} of nodes "
            f"(component sizes {[len(c) for c in components[:5]]}). "
            f"This is a severed network, not one-way traps — check network_type, "
            f"the download extent, and whether a bridge is missing."
        )

    G = G.subgraph(largest).copy()
    print(f"  routable graph: {len(G.nodes):,} nodes ({share:.2%} kept, "
          f"{len(components) - 1} components dropped)")
    assert nx.is_strongly_connected(G)
    return G


def route_many(G, pairs, *, weight="length"):
    """Route every pair — no try/except needed, because the graph guarantees a path."""
    Gp = ox.project_graph(G)
    results = []
    for (ox_, oy), (dx, dy) in pairs:
        o = ox.nearest_nodes(Gp, ox_, oy)
        d = ox.nearest_nodes(Gp, dx, dy)
        cost = 0.0 if o == d else nx.shortest_path_length(G, o, d, weight=weight)
        results.append({"origin": o, "destination": d, weight: round(cost, 1)})
    return results


G = routable(G_full)
out = route_many(G, pairs)
print(f"  {len(out)} routes, none failed")

  routable graph: 4,985 nodes (99.34% kept, 27 components dropped)
  4000 routes, none failed

The share < 0.9 guard is what separates the two situations. Dropping 0.7% of nodes to one-way traps is routine. Dropping 40% means something structural is wrong — a missing bridge, the wrong network type, a truncated download — and silently continuing would hide it behind a plausible result.

Example 3 — when a large component really is severed

def component_geography(G, path=None):
    """Where are the components? Two large ones mean a real barrier."""
    import geopandas as gpd

    components = sorted(nx.strongly_connected_components(G), key=len, reverse=True)
    nodes, _ = ox.graph_to_gdfs(ox.project_graph(G))

    membership = {}
    for i, component in enumerate(components):
        for node in component:
            membership[node] = i
    nodes["component"] = nodes.index.map(membership)

    big = [i for i, c in enumerate(components) if len(c) > 20]
    print(f"  {len(components)} components; {len(big)} with more than 20 nodes")

    for i in big[:4]:
        subset = nodes[nodes["component"] == i]
        bounds = subset.total_bounds
        print(f"    component {i}: {len(subset):5,} nodes, "
              f"extent {bounds[2] - bounds[0]:6,.0f} x {bounds[3] - bounds[1]:6,.0f} m")

    if len(big) > 1:
        print("  -> two or more substantial components: look for a river, a railway, "
              "or a motorway with no crossing inside the extract")

    if path:
        nodes.to_file(path, driver="GPKG")
    return nodes


component_geography(G_full)

  28 components; 1 with more than 20 nodes
    component 0: 4,985 nodes, extent  5,054 x  5,006 m

One substantial component means one-way traps only — the normal case, and restricting is entirely safe.

Two components of comparable size and comparable extent means a genuine severance. Writing the nodes to a GeoPackage and colouring by component makes it obvious in seconds: the boundary between them traces the barrier.

Example 4 — where the stranded nodes are

import geopandas as gpd


def map_stranded(G, path=None):
    largest = max(nx.strongly_connected_components(G), key=len)
    nodes, _ = ox.graph_to_gdfs(ox.project_graph(G))        # metres, not degrees

    nodes["stranded"] = ~nodes.index.isin(largest)
    nodes["in_degree"] = [G.in_degree(n) for n in nodes.index]
    nodes["out_degree"] = [G.out_degree(n) for n in nodes.index]

    stranded = nodes[nodes["stranded"]].copy()
    centre = nodes.geometry.union_all().centroid
    stranded["dist_from_centre_m"] = stranded.distance(centre)

    edge_share = (stranded["dist_from_centre_m"]
                  > nodes.distance(centre).quantile(0.9)).mean()
    print(f"  {len(stranded)} stranded nodes")
    print(f"  {edge_share:.0%} of them are in the outer 10% of the extract")
    print(stranded[["in_degree", "out_degree"]].value_counts().head(4).to_string())

    if path:
        stranded.to_file(path, driver="GPKG")
    return stranded


stranded = map_stranded(G_full)

  33 stranded nodes
  12% of them are in the outer 10% of the extract
in_degree  out_degree
1          0             10
0          1              6
1          1              5
0          2              3

Twelve percent of the stranded nodes are in the outer tenth of the extract — about what a random scatter would give — so in this graph they are features of central Manchester's one-way system rather than boundary artefacts. The degree table shows what they are: ten nodes with an entrance and no exit, six with an exit and no entrance. Writing them to a GeoPackage and opening them over a basemap shows which kind you have: on the rim, a buffer fixes them; spread through the centre, only restricting to the largest component will.

Why a few stranded nodes cause most failures

Why weak connectivity is not enough

nx.is_connected does not exist for directed graphs. The natural substitute, nx.is_weakly_connected, ignores edge direction — and for a street network it is nearly always True, because the underlying streets do form one connected shape.

That check therefore passes on a graph with 28 strongly connected components and 33 nodes that cannot be left. It answers "is this network one piece", which is not the question routing asks.

Strong connectivity is the routing question: can every node reach every other, following the direction of travel.

Why 33 nodes out of 5,018 cause so many failures

A geocoded address snaps to the nearest node with no awareness of whether that node can be left, and the stranded nodes are not tucked away in a corner you could avoid: in this extract only 12% of them are in its outer tenth, about what a random scatter would give (Example 4), so they sit among the routable nodes your origins snap to.

Route from twenty stranded nodes to ten random routable ones, in the unrestricted graph:

rng = np.random.default_rng(3)
stranded_nodes = [n for n in G_full.nodes if n not in largest_scc]
targets = rng.choice(list(largest_scc), 10)
failures = sum(1 for a in stranded_nodes[:20] for b in targets if not nx.has_path(G_full, a, b))
print(f"{failures} of 200 routes from stranded nodes fail ({failures / 200:.0%})")

120 of 200 routes from stranded nodes fail (60%)

So a small fraction of nodes produces a large fraction of failures, and because they are scattered, the failures look sporadic rather than structural. That is what makes people re-download the graph instead of checking connectivity.

Why the download boundary creates them

A one-way loop whose outbound leg is inside your extract and whose return runs 50 m outside it produces exactly this failure. Inside the graph the outbound exists and the return does not, so every node along it can be entered and never left.

That is the diagnostic: boundary artefacts move when you resize the download, and features of the real street network do not. In this Manchester extract a 1.5 km buffer removed only two of 24 stranded nodes from the study area (step 4): most were the city's own one-way traps.

The mitigation is a buffer: download more than you analyse, so the severed edges fall outside the region you care about. truncate_by_edge=True helps too, by keeping boundary-crossing edges whole.

Why restricting is better than catching

Catching NetworkXNoPath per pair works and leaves you with an unknown number of missing results, silently excluded from whatever you aggregate afterwards. A median over the routes that succeeded is biased toward the well-connected.

Restricting the graph moves the loss to a single, reported, up-front number — "dropped 33 stranded nodes (0.66%)" — and makes every subsequent call succeed. The stranded points are then a small, inspectable set rather than a scatter of holes in the results.

The only case where catching is right is when you cannot restrict: an analysis that must report on specific fixed locations, some of which are genuinely unreachable. Then the unreachable ones are a finding, and they should be reported as one.

Restrict before snapping, and real barriers

• nx.is_weakly_connected is nearly always True and tells you nothing about routability.
• Restrict, then snap. Snapping first can leave an endpoint pointing at a removed node, producing NodeNotFound instead.
• subgraph() returns a read-only view. Call .copy().
• has_path is much cheaper than a caught exception in a loop over many pairs.
• An undirected path existing proves the streets are present and the failure is directional.
• Stranded nodes that move when you resize the download are boundary artefacts; the ones that stay are the city's one-way system. Here 22 of 24 stayed.
• Two large components mean a real barrier — a river, railway or motorway with no crossing inside the extract.
• The walk network almost never fails — one strongly connected component, because pedestrians ignore one-way restrictions.
• Truncated downloads look like missing streets. Set ox.settings.log_console = True to see the Overpass remark that says the result was cut short.

Internal links

• Street networks as graphs explained — weak versus strong connectivity
• How to build a street network graph in Python with OSMnx — buffering to reduce the artefacts
• How to calculate the shortest path along a street network — routing once the graph is sound
• How to snap points to a street network in Python — snapping after restricting
• Street network routing returns absurd distances — the other routing failure
• How to measure network distance for many origin-destination pairs — where unreachable pairs bias an aggregate
• How to clean line network dangles in Python — the same problem in vector form

FAQ

Why does routing fail between two nearby streets?

The origin or destination is outside the largest strongly connected component — typically a cul-de-sac on a one-way, or a street severed by the download boundary.

How do I check whether a path exists?

nx.has_path(G, origin, destination) — one traversal, returns a bool, far cheaper than catching the exception from a full Dijkstra.

How do I stop this happening at all?

Restrict the graph to its largest strongly connected component before routing. Inside one, every pair has a path by definition.

Why do I get NodeNotFound after restricting the graph?

You snapped before restricting, so the endpoint references a node that was removed. Restrict first, then snap to the reduced graph.

An undirected path exists but a directed one does not. What does that mean?

The streets are present and the failure is about direction — one-way restrictions or a severed return leg. Re-downloading will not help.

Is dropping 0.7% of nodes acceptable?

Yes, and it is routine. Dropping 40% is not — that indicates a severed network, the wrong network_type, or a truncated download.

Do the stranded nodes change when I resize the download?

The ones that change are boundary artefacts, cut off by the edge of the download; the ones that stay are real one-way traps. In the Manchester study area, 22 of 24 stayed when the download grew by 1.5 km, so a buffer helps less than you might hope and restricting to the largest component is still needed.