Finding Weighted Shortest Paths in NetworkX with Dijkstra's Algorithm

Use NetworkX's shortest_path with a weight argument

The quickest way to obtain the lowest‑cost route between two nodes in a weighted graph is to call nx.shortest_path(G, source, target, weight='weight'). The function returns a list of node identifiers that form the path with the smallest sum of edge weights, using Dijkstra’s algorithm when all weights are non‑negative.

Worked example: building a weighted undirected graph

First, create a graph, add edges, and assign a numeric weight attribute to each edge. The attribute name must match the string passed to the weight parameter.

import networkx as nx

# Create an undirected graph
G = nx.Graph()

# Add edges with a 'weight' attribute
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 shortest path from A to E using the weight attribute
path = nx.shortest_path(G, source='A', target='E', weight='weight')
print('Shortest path:', path)
# Expected output: ['A', 'C', 'B', 'D', 'E'] (total weight = 2+1+5+2 = 10)

The example shows how each edge’s weight influences the result. If you omit the weight argument, NetworkX treats every edge as having weight 1 and returns the path with the fewest hops.

How the mechanism works

When weight='weight' is supplied, NetworkX looks up the weight attribute on each edge. It then runs Dijkstra’s algorithm, which repeatedly selects the unvisited node with the smallest tentative distance, updates neighbours, and stops when the target node is reached. The algorithm guarantees an optimal path only when all edge weights are zero or positive.

Limits and error conditions

• No path: If source and target are disconnected, nx.shortest_path raises nx.NetworkXNoPath.
• Negative weights: Supplying any edge with a negative weight triggers a ValueError because Dijkstra’s algorithm is not valid for negative numbers.
• Missing attribute: Edges without the specified weight attribute default to weight 1, which may produce a path that does not reflect your intended costs.

Common mistakes and how to avoid them

• Forgetting to set the weight attribute on edges, leading to the unweighted version being used inadvertently.
• Applying the function to a directed graph (nx.DiGraph) while ignoring edge direction; the algorithm respects direction automatically, but you must ensure edges are added with the correct orientation.
• Using the outdated signature shortest_path(G, source, target, weight=None) from NetworkX 2.x; in version 3.x the parameter name remains weight but the default behavior changed, so explicitly pass the attribute name.

Practical verification steps

1. Run the code snippet above in a Python environment where NetworkX 3.x is installed.
2. Confirm that the printed path matches the expected lowest‑cost route (you can manually compute the sum of weights to verify).
3. Alter one edge’s weight—for example, increase G['B']['D']['weight'] from 5 to 20—and rerun the function; the returned path should change to avoid the now‑costly edge.
4. Introduce a negative weight on any edge and observe the ValueError; this confirms the algorithm’s restriction.
5. Remove the weight attribute from an edge and note how the path shifts, illustrating the default‑to‑1 behavior.