NetworkX Dijkstra vs A* for Route Calculation

The choice between Dijkstra and A* in NetworkX comes down to a single engineering question: can you supply a heuristic that is mathematically guaranteed never to overestimate the true remaining cost? This page addresses that specific decision point as part of NetworkX shortest path algorithms for logistics, and fits within the broader Python Routing Engines & Isochrone Mapping workflow covering routing engine selection and graph construction. When coordinates are clean and edge weights track physical distance, A* is almost always faster — typically a 3–8× reduction in node expansions. When edge weights encode composite logistics costs (turn penalties, tolls, time-of-day traffic), Dijkstra is the safer default.

When to Use This Approach

Both algorithms share the same min-heap priority queue mechanics and return identical optimal paths on well-formed graphs. Their behaviour diverges based on the graph’s structure and the semantics of edge weights.

Choose A* when:

• Every node carries reliable lat and lon attributes
• Edge weights represent or strongly correlate with physical distance or travel time at constant speed
• You need sub-second routing on graphs with more than 10 000 nodes
• You can prove the heuristic is admissible for all possible edge cost configurations

Choose Dijkstra when:

• Edge weights encode composite logistics costs: turn penalties, congestion pricing, fuel consumption, access tag overrides
• The graph contains disconnected components or isolated subgraphs — common after filtering OSM data by highway tag class
• Heuristic admissibility cannot be mathematically guaranteed (e.g., traffic multipliers may reduce costs below the heuristic’s lower bound)
• Coordinate data is missing, approximate, or projected into an unfamiliar CRS
• You are implementing fallback routing for degraded GPS input

In dense urban delivery grids with simple distance weights, A* dominates. On networks where the process of configuring edge weights for freight logistics has layered in vehicle class restrictions, time windows, and regulatory penalties, the heuristic breaks down and Dijkstra is the correct choice.

Implementation

The snippet below benchmarks both algorithms on a synthetic geospatial graph using a Haversine heuristic. It is self-contained and focuses on the comparison — graph construction patterns shared with the parent cluster are not repeated here.

# Requirements: pip install networkx
# Python 3.9+  |  networkx >= 3.0

import networkx as nx
import math
import time
from typing import Callable


def haversine_km(lat1: float, lon1: float, lat2: float, lon2: float) -> float:
    """Great-circle distance in km — admissible heuristic for road routing."""
    R = 6371.0
    dlat = math.radians(lat2 - lat1)
    dlon = math.radians(lon2 - lon1)
    a = (math.sin(dlat / 2) ** 2
         + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2))
         * math.sin(dlon / 2) ** 2)
    return R * 2 * math.asin(math.sqrt(a))


def build_sample_graph() -> nx.Graph:
    """Synthetic LA-area coordinate graph with distance-based edge weights."""
    G = nx.Graph()
    nodes = {
        0: (34.0522, -118.2437),
        1: (34.0600, -118.2500),
        2: (34.0700, -118.2300),
        3: (34.0800, -118.2400),
        4: (34.0900, -118.2200),
        5: (34.1000, -118.2500),
    }
    for nid, (lat, lon) in nodes.items():
        G.add_node(nid, lat=lat, lon=lon)

    edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 3), (1, 4), (2, 5)]
    for u, v in edges:
        dist = haversine_km(
            G.nodes[u]["lat"], G.nodes[u]["lon"],
            G.nodes[v]["lat"], G.nodes[v]["lon"],
        )
        G.add_edge(u, v, weight=dist)
    return G


def make_heuristic(G: nx.Graph) -> Callable[[int, int], float]:
    """Return a closure over G so NetworkX can call heuristic(u, v)."""
    def heuristic(u: int, v: int) -> float:
        return haversine_km(
            G.nodes[u]["lat"], G.nodes[u]["lon"],
            G.nodes[v]["lat"], G.nodes[v]["lon"],
        )
    return heuristic


G = build_sample_graph()
source, target = 0, 5
heuristic = make_heuristic(G)

# --- Dijkstra ---
t0 = time.perf_counter()
d_path = nx.dijkstra_path(G, source, target, weight="weight")
d_cost = nx.dijkstra_path_length(G, source, target, weight="weight")
d_time = time.perf_counter() - t0

# --- A* ---
t0 = time.perf_counter()
a_path = nx.astar_path(G, source, target, heuristic=heuristic, weight="weight")
a_cost = nx.astar_path_length(G, source, target, heuristic=heuristic, weight="weight")
a_time = time.perf_counter() - t0

print(f"Dijkstra : {d_path}  cost={d_cost:.4f} km  time={d_time*1000:.3f}ms")
print(f"A*       : {a_path}  cost={a_cost:.4f} km  time={a_time*1000:.3f}ms")
print(f"Paths match: {d_path == a_path}")
print(f"Costs match: {abs(d_cost - a_cost) < 1e-9}")

Handling directed graphs. One-way streets require a DiGraph. Both algorithms work unchanged on directed NetworkX graphs — pass a DiGraph built with one-directional edges and neither function needs modification. For more detail on correctly encoding oneway=yes tags see handling one-way streets in Python NetworkX.

Key Parameters and Tuning

Coordinate system choice. For regions under 50 km across, projecting to a local UTM zone and using Euclidean distance as the heuristic reduces math.asin / math.sqrt CPU overhead by roughly 40 % without sacrificing admissibility. Use pyproj.Transformer to reproject coordinates once during graph construction rather than on every heuristic call.

Admissibility vs. consistency. An admissible heuristic guarantees that A* returns an optimal path. A consistent (monotone) heuristic additionally guarantees that each node is expanded at most once, making the algorithm more efficient. Haversine distance is both admissible and consistent on undirected graphs with symmetric weights. On directed graphs, verify that h(u) ≤ cost(u, v) + h(v) holds across every directed edge before deploying A* in production.

Dynamic edge weights. When the weight callable encodes time-of-day traffic multipliers, the heuristic must bound the minimum possible traversal cost, not the average. If traffic occasionally drops travel time below free-flow speed (for example during off-peak hours with a safety buffer applied in the wrong direction), the heuristic will overestimate and A* may return suboptimal routes silently. Profile this against your traffic data distributions before committing to A*.

Integration Points

Both algorithms return node-ID lists. Connecting that output to downstream systems requires a few deliberate steps:

Extracting geometry. After computing a path, reconstruct the coordinate sequence for rendering or distance calculation:

# Python 3.9+  |  networkx >= 3.0

def path_to_coords(G: nx.Graph, path: list[int]) -> list[tuple[float, float]]:
    return [(G.nodes[n]["lat"], G.nodes[n]["lon"]) for n in path]

coords = path_to_coords(G, d_path)
total_km = sum(
    haversine_km(coords[i][0], coords[i][1], coords[i+1][0], coords[i+1][1])
    for i in range(len(coords) - 1)
)

Feeding OSRM or Valhalla for snapped routing. NetworkX graph paths computed over a simplified node topology often need to be re-snapped to the full road network before being passed to a production engine. The deploying OSRM with Docker for local routing workflow describes how to snap waypoints and request turn-by-turn geometry from OSRM’s /match endpoint using the NetworkX path as an ordered waypoint sequence.

Isochrone construction. Dijkstra’s single_source_dijkstra_path_length() is the standard entry point for isochrone generation — it returns cost-to-all-nodes in one pass, which can then be filtered by a cost threshold and passed to a polygon hull algorithm. This is the foundation of the generating isochrones with PySAL and GeoPandas workflow.

Graph scale thresholds. For graphs above roughly 500 000 nodes, the Python overhead of NetworkX’s pure-Python priority queue becomes the bottleneck. At that scale, consider exporting the graph to a compiled engine: OSRM for road routing or Valhalla configuration for multi-modal analysis for transit-aware routing. For an in-process alternative with a C++ backend, igraph or graph-tool expose similar shortest-path APIs with 10–50× lower per-operation overhead.

Validation Checklist

Run these checks after integrating either algorithm into a routing pipeline:

1. Path equivalence on a known graph. On any graph where the heuristic is provably admissible, nx.dijkstra_path(G, s, t) == nx.astar_path(G, s, t, heuristic) must hold. If it does not, the heuristic is overestimating — inspect the edge with the highest cost relative to its geometric length.

2. Cost equivalence. abs(dijkstra_path_length - astar_path_length) < 1e-9 must hold. Floating-point rounding is acceptable; a difference of more than 1e-6 km indicates a heuristic admissibility violation.

3. Directed graph correctness. On a DiGraph with known one-way edges, confirm the returned path never traverses an edge in the wrong direction. Programmatically: all(G.has_edge(path[i], path[i+1]) for i in range(len(path)-1)).

4. Disconnected graph handling. Both algorithms raise nx.NetworkXNoPath when no path exists. Wrap calls in a try/except nx.NetworkXNoPath block and verify that disconnected subgraphs are detected correctly. Consider graph fragmentation prevention in OSM data if your OSM-derived graph has unexpected component splits.

5. Heuristic non-negativity. Assert heuristic(u, v) >= 0 for a random 1 % sample of node pairs. Negative heuristic values will silently corrupt A*'s priority queue ordering.

6. Performance regression gate. On your production graph, record median query time for both algorithms over 500 random source-target pairs. If A* is slower than Dijkstra on more than 20 % of pairs, the heuristic is providing insufficient guidance — re-examine coordinate accuracy or CRS consistency.

Related

• NetworkX shortest path algorithms for logistics — parent reference covering algorithm selection, multi-source variants, and weight callback patterns
• Handling one-way streets in Python NetworkX — encoding oneway=yes as directed edges so Dijkstra and A* respect travel direction
• Generating isochrones with PySAL and GeoPandas — using Dijkstra’s single-source variant as the cost-distance input for isochrone polygon construction
• Deploying OSRM with Docker for local routing — when NetworkX graphs exceed scale thresholds, transitioning to OSRM’s compiled routing pipeline