NetworkX Says No Path Exists Between Two Nodes

Problem statement

Two addresses a few streets apart, and routing fails:

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

networkx.exception.NetworkXNoPath: No path between 25497624 and 1521274653.

You can see both streets on a map. You can walk between them in four minutes. The graph has 4,935 nodes and both of them are 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.

Check	Meaning if it fails
`origin in largest_scc`	the origin is stranded
`G.out_degree(origin) == 0`	you can arrive and not leave
`G.in_degree(destination) == 0`	you can leave and not arrive
`nx.has_path(G, o, d)`	the definitive test, cheap
`G.is_directed()`	an undirected graph would have routed

Five causes of NetworkXNoPath: stranded origin, stranded destination, zero out-degree, wrong network type, and a graph clipped mid-route. — All five are structural. None means the streets are missing from OpenStreetMap.

Step-by-step solution

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

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.67%)

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. 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.

5. 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 :  4,935 nodes,  28 components
walk  : 25,919 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.

Snapping before restricting the graph leaves an endpoint pointing at a removed node; snapping after guarantees it is routable. — Order matters. Restrict first, then snap, or the endpoint can reference a node that no longer exists.

Code examples

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, 25497624, 1521274653)

  origin 25497624: out-degree 0, in-degree 1
  destination 1521274653: out-degree 2, 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 4902 (largest is 4902)
  ✗ 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)
out = route_many(G, pairs)
print(f"  {len(out)} routes, none failed")

  routable graph: 4,902 nodes (99.33% kept, 27 components dropped)
  4,000 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)

  28 components; 1 with more than 20 nodes
    component 0: 4,902 nodes, extent  4,914 x  4,988 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.

Explanation

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 4,935 cause so many failures

Stranded nodes are not distributed randomly among your queries. Around three-quarters of them sit in the outer tenth of the extract, and a geocoded address snaps to the nearest node with no awareness of whether that node can be left.

Measured over 200 random routes originating at stranded nodes:

120 of 200 routes 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.

Two nodes with no directed path but a clear undirected one, proving the streets exist and the problem is one-way direction. — An undirected path existing is proof that the streets are there. The failure is direction, not data.

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.

The boundary is arbitrary, so the artefacts are arbitrary. Change dist from 2 km to 3 km and a different set of nodes is stranded — which is the diagnostic. Features of the real street network do not move when you resize the download.

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.67%)" — 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.

Edge cases or notes

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 move when you change the download size. That instability identifies them as boundary artefacts.
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.

Internal links

Your street network graph is disconnected or missing streets — diagnosing the graph rather than the pair
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.

Why do the stranded nodes change when I resize the download?

Because most are boundary artefacts rather than features of the street network. That instability is how you tell the two apart.

NetworkX Says No Path Exists Between Two Nodes #

Problem statement #

Quick answer #

Step-by-step solution #

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

2. Use has_path, not a try/except #

3. Restrict the graph to its largest strongly connected component #

4. Re-snap your endpoints afterwards #

5. Check you are not simply on the wrong network #

Code examples #

Example 1 — a diagnostic for a specific failure #

Example 2 — a pipeline that cannot produce the exception #

Example 3 — when a large component really is severed #

Explanation #

Why weak connectivity is not enough #

Why 33 nodes out of 4,935 cause so many failures #

Why the download boundary creates them #

Why restricting is better than catching #

Edge cases or notes #

Internal links #

FAQ #

Why does routing fail between two nearby streets? #

How do I check whether a path exists? #

How do I stop this happening at all? #

Why do I get NodeNotFound after restricting the graph? #

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

Is dropping 0.7% of nodes acceptable? #

Why do the stranded nodes change when I resize the download? #