Weighted shortest path limits: handling missing weights and negative edges in NetworkX

Answer

In short, NetworkX’s current design – silent default weight of 1, no automatic algorithm switching, and no error on missing attributes – is intentional and works for most use‑cases. It places the responsibility on the caller to pick the right routine and to supply explicit weights. Adding automatic safeguards would introduce new runtime costs, break backward compatibility, and give users a false sense of security. Therefore, the library should continue to do nothing special and the user should be encouraged to:

• explicitly choose dijkstra_path or bellman_ford_path based on the presence of negative weights or cycles;
• provide a weight attribute on every edge or set a global default via weight=... when calling the routine;
• use MultiGraph only when the minimum‑weight semantics are intended.

Why the current design is acceptable

NetworkX aims for a lightweight, flexible API. The default weight of 1 keeps the functions usable on unweighted graphs without extra boilerplate. Automatic switching to Bellman‑Ford would mean a graph is first scanned for negative edges, incurring extra O(|E|) work and potentially selecting an algorithm that is sub‑optimal for dense graphs. Moreover, the presence of a negative cycle is a property that is only meaningful in the context of the algorithm being used – a graph that is fine for Dijkstra may still contain a harmless negative edge if the user never expects negative weights.

When to consider a change

If a project’s domain guarantees that all edges carry a non‑negative weight and the graph is large, a developer might want a safety net that warns about missing weights. In that niche scenario, adding a check_missing_weights=True flag to the shortest‑path functions would be a lightweight addition. However, a blanket enforcement would be too restrictive.

Verification checklist

1. Run nx.dijkstra_path(G, source, target, weight='weight') on a graph that contains a negative edge and confirm the returned path is not optimal.

2. Run nx.bellman_ford_path(G, source, target, weight='weight') on the same graph; verify that the path is correct and that NetworkXUnbounded is raised if a negative cycle is reachable.

3. Create a graph with an edge missing the weight attribute, call nx.shortest_path_length(G, source, target, weight='weight'), and check that the algorithm treats that edge as weight 1.

4. Construct a MultiGraph with parallel edges of different weights; confirm that the algorithm uses the minimum weight among the parallel edges.

5. If you want to enforce a different default, set weight=DEFAULT when calling the routine or pre‑populate every edge with the desired weight.

These tests are quick to run and will confirm that the library behaves as documented. If you discover a negative cycle in your data, you can then decide whether to switch to Bellman‑Ford or preprocess the graph to remove the cycle.