NetworkX Shortest Path Algorithms for Logistics

Logistics engineers and GIS developers frequently encounter routing problems that extend well beyond simple point-to-point navigation. When optimizing delivery fleets, planning emergency response corridors, or auditing freight accessibility across urban zones, you need direct control over graph topology, edge weights, and constraint modeling — capabilities that commercial routing APIs rarely expose. As part of the broader Python Routing Engines & Isochrone Mapping engineering stack, NetworkX serves as the analytical layer where routing logic is validated, iterated, and proven correct before being handed off to production-scale solvers such as OSRM or Valhalla.

This page covers the full workflow: environment setup, topology ingestion, vectorized cost-function assignment, algorithm selection, geometry extraction, production scaling, and regression testing — with logistics-specific calibration notes at every step.

Architecture: How NetworkX Fits the Routing Pipeline

Before writing code, understand where NetworkX lives relative to the broader toolchain. The diagram below shows the data-flow from raw OSM extract to a dispatched route.

NetworkX handles the middle three stages. The OSM ingestion is delegated to OSMnx; compiled dispatch at scale migrates to deploying OSRM with Docker for local routing or Valhalla configuration for multi-modal analysis. What NetworkX provides is a fully programmable, inspectable graph where you can prototype cost functions, test constraint logic, and generate ground-truth routes against which to benchmark compiled engines.

Prerequisites

Python version, libraries, and data sources

The recommended stack for logistics-focused NetworkX implementations:

• Python 3.9+ — required for osmnx>=1.3, which drops Python 3.8 support
• networkx>=3.0 — nx.write_gpickle() was removed in 3.0; use pickle directly
• osmnx>=1.3 — provides graph_from_place, projected graph utilities, and nearest-node lookup
• geopandas>=0.13 + shapely>=2.0 — vectorized spatial operations and geometry serialization
• numpy — vectorized weight assignment across edge DataFrames
• haversine — fast great-circle distance heuristic for A*

# Required installs for the full workflow on this page
pip install networkx osmnx geopandas shapely numpy haversine

Directed graphs are mandatory

Logistics routing requires a DiGraph (or MultiDiGraph) to model oneway=yes streets, turn restrictions, and lane-specific speed limits. OSMnx returns a MultiDiGraph by default. Every algorithm on this page targets directed graphs; using an undirected Graph silently produces incorrect results on urban networks.

For a production walkthrough of enforcing one-way constraints and parsing OSM oneway attributes, see handling one-way streets in Python NetworkX.

Step-by-Step Implementation

Step 1: Network Ingestion and Topology Validation

Raw OpenStreetMap data contains topological noise — dangling nodes, disconnected micro-components from pedestrian paths clipped at the bounding box, and duplicate edges — that silently breaks pathfinding. The ingestion phase must filter for drivable infrastructure, project coordinates to a metric CRS, and prune disconnected components.

# Required: pip install osmnx networkx
import osmnx as ox
import networkx as nx

# Download drivable road network for a named place
# network_type="drive" filters to highway tags accessible by motor vehicle
G = ox.graph_from_place("Chicago, Illinois, USA", network_type="drive")

# Project from WGS-84 (degrees) to UTM (meters) — required for accurate length/speed calculations
G_proj = ox.projection.project_graph(G)

# Retain only the largest weakly connected component
# Weak connectivity checks reachability ignoring edge direction — correct for drivable networks
largest_cc = max(nx.weakly_connected_components(G_proj), key=len)
G_clean = G_proj.subgraph(largest_cc).copy()

print(f"Nodes: {G_clean.number_of_nodes():,}  Edges: {G_clean.number_of_edges():,}")

Always verify connectivity before routing. If your fleet operates within a constrained service area or depends on a single bridge or tunnel, check whether that corridor survives weakly_connected_components filtering. For strategies to prevent topology fragmentation in regional OSM extracts, see graph fragmentation prevention in OSM data.

Step 2: Vectorized Cost Function Assignment

Default implementations route by physical distance (length in metres), which rarely aligns with operational objectives. Freight networks require travel time, toll cost, vehicle restriction penalties, or fuel consumption. Assign these as edge attributes — NetworkX accepts arbitrary keys — and select them at query time via the weight parameter.

The loop pattern works for prototyping but is slow on metropolitan graphs (500 k+ edges). Use nx.set_edge_attributes with a pre-built dictionary derived from Pandas operations on the edge DataFrame for production workloads.

# Required: pip install osmnx networkx numpy pandas
import numpy as np
import pandas as pd

# Extract edge data as a DataFrame for vectorized operations
edges_df = ox.graph_to_gdfs(G_clean, nodes=False, edges=True).reset_index()

# Vectorized travel time (seconds): length_m / speed_mps
# OSMnx populates 'speed_kph' from maxspeed tags and road-type defaults
speed_mps = edges_df["speed_kph"].fillna(30) / 3.6  # fallback: 30 kph urban default
edges_df["weight_time"] = edges_df["length"] / speed_mps

# Example freight penalty: add 30 s per junction on arterials (highway=secondary)
JUNCTION_PENALTY_S = 30
is_arterial = edges_df["highway"].apply(
    lambda h: h in {"secondary", "secondary_link"} if isinstance(h, str)
    else any(x in {"secondary", "secondary_link"} for x in (h or []))
)
edges_df["weight_freight"] = edges_df["weight_time"] + JUNCTION_PENALTY_S * is_arterial.astype(int)

# Write computed weights back to the graph
time_dict   = {(r.u, r.v, r.key): r.weight_time   for r in edges_df.itertuples()}
freight_dict = {(r.u, r.v, r.key): r.weight_freight for r in edges_df.itertuples()}
nx.set_edge_attributes(G_clean, time_dict,   "weight_time")
nx.set_edge_attributes(G_clean, freight_dict, "weight_freight")

Multiple weight layers — weight_time, weight_toll, weight_risk — let you swap cost models at query time without mutating the graph. For deep guidance on OSM tag mapping and vehicle-class weight matrices, see configuring edge weights for freight logistics.

Step 3: Algorithm Selection

The right algorithm depends on graph density, whether a spatial heuristic is available, and whether any edge weights can be negative.

For dense urban networks where the destination’s geographic location is known, A* typically visits 30–60% fewer nodes than Dijkstra by steering the search toward the goal.

# Required: pip install networkx osmnx haversine
from networkx import astar_path, dijkstra_path, NetworkXNoPath
from haversine import haversine, Unit

# Snap coordinates to nearest graph nodes
origin_node = ox.distance.nearest_nodes(G_clean, X=-87.6298, Y=41.8781)
dest_node   = ox.distance.nearest_nodes(G_clean, X=-87.6245, Y=41.8819)

# Haversine heuristic for A* — must be admissible (never overestimate actual cost)
# Returns metres; consistent with weight_time only if speed ≥ 1 m/s everywhere
def haversine_heuristic(u, v):
    u_latlon = (G_clean.nodes[u]["y"], G_clean.nodes[u]["x"])
    v_latlon = (G_clean.nodes[v]["y"], G_clean.nodes[v]["x"])
    return haversine(u_latlon, v_latlon, unit=Unit.METERS)

try:
    # A* with freight cost layer
    route_nodes = astar_path(
        G_clean, origin_node, dest_node,
        heuristic=haversine_heuristic,
        weight="weight_freight"
    )
except NetworkXNoPath:
    # Destination unreachable — common cause: different weakly connected component
    route_nodes = []
    print(f"No path found between {origin_node} → {dest_node}")

Always wrap pathfinding in try...except NetworkXNoPath. Unreachable destinations are routine in freight networks with access restrictions and should not crash the dispatch loop.

For a detailed benchmarking comparison of Dijkstra and A* across metropolitan-scale graphs — including node-expansion counts, memory profiles, and heuristic admissibility testing — see NetworkX Dijkstra vs A* for route calculation.

Step 4: Route Extraction and Geometry Construction

A node-ID sequence is not a usable deliverable. Convert it to a spatial GeoDataFrame with cumulative cost metrics for dispatch systems, compliance logging, and map rendering.

# Required: pip install geopandas shapely networkx osmnx
import geopandas as gpd
from shapely.geometry import LineString
from shapely.ops import linemerge

def extract_route_geodataframe(graph: nx.MultiDiGraph, node_list: list) -> gpd.GeoDataFrame:
    """
    Convert a NetworkX node sequence to a projected GeoDataFrame with
    cumulative travel-time and freight-cost columns.
    """
    if len(node_list) < 2:
        return gpd.GeoDataFrame(columns=["geometry", "cost_time_s", "cost_freight_s"])

    segments, cost_time, cost_freight = [], 0.0, 0.0

    for u, v in zip(node_list[:-1], node_list[1:]):
        # key=0 selects the first parallel edge in a MultiDiGraph
        edge_data = graph.edges[u, v, 0]

        cost_time    += edge_data.get("weight_time",    edge_data.get("length", 0))
        cost_freight += edge_data.get("weight_freight", edge_data.get("length", 0))

        if "geometry" in edge_data:
            segments.append(edge_data["geometry"])
        else:
            # Straight-line fallback for edges without detailed OSM geometry
            segments.append(LineString([
                (graph.nodes[u]["x"], graph.nodes[u]["y"]),
                (graph.nodes[v]["x"], graph.nodes[v]["y"])
            ]))

    merged = linemerge(segments)  # merge into single LineString where possible
    return gpd.GeoDataFrame(
        {"cost_time_s": [cost_time], "cost_freight_s": [cost_freight], "geometry": [merged]},
        crs=graph.graph["crs"]
    )

route_gdf = extract_route_geodataframe(G_clean, route_nodes)
print(f"Route length: {route_gdf.geometry.length.iloc[0]:.0f} m  "
      f"Est. time: {route_gdf.cost_time_s.iloc[0]:.0f} s")

Step 5: Constraint Enforcement and Fallback Routing

When a route violates compliance rules — a bridge with a maxweight tag below your vehicle GVW, a tunnel with maxheight below your trailer — temporarily inflate affected edge weights and recompute rather than rebuilding the graph.

# Required: pip install networkx
SENTINEL_WEIGHT = 1e9  # effectively removes edges from consideration

def route_with_exclusions(graph, origin, dest, weight_key, excluded_edges):
    """
    Route around a set of (u, v, key) edge tuples by temporarily assigning
    a sentinel weight, then restoring originals afterward.
    """
    originals = {}
    for u, v, k in excluded_edges:
        originals[(u, v, k)] = graph.edges[u, v, k].get(weight_key, 0)
        graph.edges[u, v, k][weight_key] = SENTINEL_WEIGHT

    try:
        path = astar_path(graph, origin, dest,
                          heuristic=haversine_heuristic,
                          weight=weight_key)
    except NetworkXNoPath:
        path = []
    finally:
        # Always restore — even if routing raised an exception
        for (u, v, k), original in originals.items():
            graph.edges[u, v, k][weight_key] = original

    return path

# Example: exclude a low-clearance tunnel edge identified by OSM node IDs
low_clearance_edges = [(123456789, 987654321, 0)]
safe_route = route_with_exclusions(
    G_clean, origin_node, dest_node, "weight_freight", low_clearance_edges
)

For systematic modeling of node-level restrictions — loading-dock access, delivery-zone permits, urban access tags like access=delivery — see mapping node attributes for urban delivery zones.

Configuration Reference

Key parameters and their recommended values for logistics-grade NetworkX routing:

OSM tag values used in weight logic: highway=secondary, highway=motorway, oneway=yes, maxweight=*, maxheight=*, access=delivery.

Production Optimization and Scaling

NetworkX is an in-memory Python library. It excels at prototyping, mid-scale optimization (cities up to ~1 M edges), and algorithmic validation, but requires deliberate tuning beyond that threshold.

Vectorized weight assignment. The per-edge Python loop shown in Step 2 is for clarity. On a 500 k-edge metropolitan graph, use nx.set_edge_attributes with a dict built from a Pandas vectorized operation — roughly 20x faster.

Batch dispatch with multi-source Dijkstra. When a depot must compute drive times to 5 000 delivery stops, nx.multi_source_dijkstra(G, sources={depot_node}) returns a cost dict for all reachable nodes in a single pass — far more efficient than 5 000 individual dijkstra_path calls.

# Required: pip install networkx
# Single-pass cost map: depot to all reachable nodes
costs, _ = nx.multi_source_dijkstra(G_clean, sources={origin_node}, weight="weight_freight")
# costs is a dict: {node_id: cumulative_cost}
top_10 = sorted(costs.items(), key=lambda x: x[1])[:10]

Graph serialization and reload. Decouple graph construction from path computation. Build and weight the network once per OSM refresh cycle, serialize with pickle, and reload it in worker processes. This eliminates redundant OSM parsing and ensures a consistent routing baseline across distributed dispatch instances.

# Required: import pickle
import pickle

# Save (after weight assignment)
with open("chicago_freight.pkl", "wb") as f:
    pickle.dump(G_clean, f, protocol=4)

# Reload in worker
with open("chicago_freight.pkl", "rb") as f:
    G_loaded = pickle.load(f)

Compiled-solver handoff. For sub-second response at continental scale, validated NetworkX logic migrates to C+±backed engines. Deploying OSRM with Docker for local routing provides a reliable pathway for high-throughput single-modal routing. Valhalla configuration for multi-modal analysis supports complex transit, pedestrian, and bicycle integrations with configurable costing JSON.

Validation and Testing

After building a routing pipeline, verify correctness with a regression suite before deploying to a dispatch system.

Sanity checks to run on every graph build:

# Required: pip install networkx osmnx
import networkx as nx

assert nx.is_directed(G_clean), "Graph must be directed for one-way enforcement"
assert nx.is_weakly_connected(G_clean), "Graph must be a single connected component"

# All weight values must be positive and finite
import math
for u, v, data in G_clean.edges(data=True):
    w = data.get("weight_freight", 0)
    assert w > 0 and math.isfinite(w), f"Invalid weight on edge ({u}, {v}): {w}"

# Confirm A* produces same cost as Dijkstra for known pair (heuristic admissibility check)
from networkx import astar_path_length, dijkstra_path_length
astar_cost    = astar_path_length(G_clean, origin_node, dest_node,
                                  heuristic=haversine_heuristic, weight="weight_freight")
dijkstra_cost = dijkstra_path_length(G_clean, origin_node, dest_node, weight="weight_freight")
assert abs(astar_cost - dijkstra_cost) < 1e-6, \
    f"Heuristic is inadmissible: A*={astar_cost:.2f}, Dijkstra={dijkstra_cost:.2f}"

print("All validation checks passed.")

Regression patterns for CI:

• Store a set of canonical (origin_lat, origin_lon, dest_lat, dest_lon, expected_cost_s) tuples derived from GPS-trace ground truth.
• After each OSM data refresh, recompute and assert costs are within ±5% of baseline — larger deviations indicate OSM topology changes that need weight-function review.
• Log the node count, edge count, and average degree after each build; unexpected drops signal topology fragmentation.

For isochrone-based reachability validation — confirming that the set of nodes within a given travel-time budget matches known service areas — see generating isochrones with PySAL and GeoPandas.

Troubleshooting

Related

• NetworkX Dijkstra vs A* for route calculation — benchmark comparison with node-expansion counts and heuristic admissibility analysis
• Handling one-way streets in Python NetworkX — directed-graph enforcement for oneway=yes and lane-specific restrictions
• Configuring edge weights for freight logistics — OSM tag mapping, vehicle-class matrices, and multi-layer weight schemas
• Deploying OSRM with Docker for local routing — compiled-solver handoff for production-throughput routing
• Custom cost functions for routing solvers — generalised penalty design across NetworkX, OSRM, and Valhalla