Weighted shortest paths in NetworkX: Dijkstra, edge weights, and verification

The problem: choosing a route when roads have different costs

Imagine a delivery network modeled as a directed graph. Nodes are locations, and edges are roads. Each road has a cost attribute representing time, fuel, or tolls. You need the cheapest route from the warehouse to the store, but not every road records the same attribute, and some roads might not list a cost at all.

NetworkX provides dijkstra_path for this scenario, but it behaves predictably only when edge weights are non-negative and you explicitly tell it which attribute to read. The useful takeaway: specify the weight attribute, verify the returned path by summing the edge attributes yourself, and switch algorithms when weights are negative or the graph is unweighted.

How NetworkX reads edge weights

nx.dijkstra_path(G, source, target, weight="weight") finds the lowest-cost path using Dijkstra's algorithm. By default it looks for an edge attribute named weight. If an edge lacks that attribute, NetworkX treats its weight as one. You can pass a different attribute name, such as cost, or even a callable that computes weight from the edge data.

Dijkstra's algorithm assumes every edge weight is zero or positive. Negative weights can produce incorrect distances without a guaranteed error, so they are outside its contract.

Worked example: warehouse to store

Run this in an activated virtual environment where NetworkX is installed. No special permissions are required.

import networkx as nx

G = nx.DiGraph()
G.add_edge("warehouse", "hub", cost=4)
G.add_edge("hub", "store", cost=2)
G.add_edge("warehouse", "store", cost=10)
G.add_edge("hub", "depot", cost=1)

path = nx.dijkstra_path(G, "warehouse", "store", weight="cost")
total = sum(
    G[u][v].get("cost", 1) for u, v in zip(path, path[1:]
)
length = nx.single_source_dijkstra_path_length(
    G, "warehouse", weight="cost"
)["store"]

print(path)
print(total)
print(length)

Check that path starts at "warehouse", ends at "store", and that every consecutive pair is an edge in G. The independently summed total should match length. If an edge omits cost, the algorithm treats it as one, but direct dictionary access would raise KeyError; that is why the example uses .get("cost", 1) for verification.

To confirm the installed behavior before relying on it, run:

python -c "import networkx as nx; print(nx.__version__)"

Record the version and review its release notes for shortest-path changes after an upgrade.

Trade-offs and limitations

• In-memory pure Python. NetworkX graphs live in RAM and are best for small to medium graphs. Large production workloads usually need a dedicated graph database or specialized graph engine.
• No negative weights. If your data contains negative edge weights, use nx.bellman_ford_path_length instead, provided there are no negative cycles.
• Unweighted graphs. If you only need the fewest hops, nx.shortest_path uses breadth-first search and avoids priority-queue overhead.
• Version drift. Default attribute handling and performance can change between NetworkX releases, so verify after upgrades.

Actionable closing

1. Check your NetworkX version with the command above.
2. Model your network with explicit edge attributes, then call dijkstra_path with the matching weight name.
3. Verify by summing G[u][v].get(weight_attribute, 1) along the returned node sequence and comparing it to single_source_dijkstra_path_length.
4. Use BFS for unweighted hop counts and Bellman-Ford when negative weights are present.

This verification step takes seconds and protects you from silent mistakes when edge attributes are missing or inconsistent.