Computing Weighted Shortest Paths in NetworkX with Dijkstra’s Algorithm

Quick answer

To obtain the lowest‑cost node sequence between two vertices in a NetworkX graph, call nx.shortest_path(G, source, target, weight='weight'). When a weight key is supplied, the function internally runs Dijkstra’s algorithm and returns the path with the minimum sum of the specified edge attribute.

How the algorithm works

Dijkstra’s method maintains a priority queue of (tentative_distance, node) pairs. It repeatedly extracts the node with the smallest distance, relaxes all outgoing edges (updating the neighbor’s distance if a shorter route is found), and stops when the target node is removed from the queue or the queue becomes empty. The implementation assumes:

• The graph is a Graph or DiGraph (or a MultiGraph/MultiDiGraph where an edge key is given).
• All edge weights are non‑negative numbers.
• Every edge that may participate in the path possesses the attribute named by the weight argument.

The time complexity is O((V+E) log V); if no path exists the function returns None.

Worked example

Consider a directed graph with four nodes and the following weighted edges:

import networkx as nx

G = nx.DiGraph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'C', weight=1)
G.add_edge('B', 'D', weight=5)
G.add_edge('C', 'D', weight=8)
G.add_edge('C', 'E', weight=10)
G.add_edge('D', 'E', weight=2)

# Compute the weighted shortest path from A to E
path = nx.shortest_path(G, source='A', target='E', weight='weight')
print(path)  # Expected: ['A', 'C', 'B', 'D', 'E'] (cost 2+1+5+2 = 10)

In this example the algorithm explores:

1. Start at A (distance 0).
2. Push B (4) and C (2) onto the queue.
3. Extract C (distance 2), relax its edges: D gets 10, E gets 12.
4. Extract B (distance 4), relax: C sees a better distance 5 (ignored), D gets 9 (better than 10).
5. Extract D (distance 9), relax: E gets 11 (better than 12).
6. Extract E (distance 11) – target reached.

The returned node list ['A', 'C', 'B', 'D', 'E'] corresponds to the minimum‑cost route.

Limits and common mistakes

Missing weight attribute

If an edge lacks the specified weight key, NetworkX raises a KeyError (in recent versions) or silently treats the weight as 1 in older releases. This can lead to unexpected paths or runtime errors.

Negative weights

Dijkstra’s algorithm is not correct for negative edge weights. Supplying them yields a path that may not be optimal, and the function does not warn you. For graphs with negative weights use nx.algorithms.shortest_paths.weighted.bellman_ford_path instead.

Multigraphs without an edge key

When working with MultiGraph or MultiDiGraph, multiple edges can exist between the same node pair. If you do not specify which edge to consider (via the key parameter in the weight lookup), the algorithm may pick an arbitrary edge, producing ambiguous results. Always provide a concrete key or collapse parallel edges before running the shortest‑path query.

Modifying the graph during iteration

Altering the graph (adding/removing nodes or edges) while iterating over the result of nx.shortest_path or similar functions can corrupt internal state and lead to exceptions or incorrect outputs. Perform modifications only after you have finished using the path.

Practical verification steps

1. Manual check on a tiny graph: Build a triangle with edges A‑B (1), B‑C (2), A‑C (4). The cheapest route from A to C is A‑B‑C (cost 3). Run nx.shortest_path(G, 'A', 'C', weight='weight') and confirm the returned list matches ['A', 'B', 'C'].
2. Cross‑function consistency: Compare the output of nx.shortest_path with the lower‑level nx.algorithms.shortest_paths.weighted.dijkstra_path(G, source, target, weight='weight'). They should return identical node lists for the same inputs.
3. Reachability test: Verify that nx.has_path(G, source, target) is True whenever a path is returned, and False when the function yields None. This catches cases where the graph is disconnected.

Summary

Use nx.shortest_path(..., weight='weight') for weighted shortest paths when all edge weights are non‑negative and every relevant edge carries the specified attribute. Verify results on small, hand‑calculated graphs, compare with the dedicated Dijkstra implementation, and ensure reachability checks agree. Avoid negative weights, missing attributes, and concurrent graph modifications to keep the algorithm behaving as expected.