TopolearnRouting, degrees of separation and dependency distances are all shortest-path questions.
nx.shortest_path(G, source, target) returns one shortest path as a list of nodes, and nx.shortest_path_length(G, source, target) its length. Without a weight, this is breadth-first search and length counts edges. With weight="km", NetworkX uses Dijkstra's algorithm, which requires non-negative weights. For negative weights use nx.bellman_ford_path, which also detects negative cycles.
Variants:
- Leave out
targetto get paths from the source to every reachable node, as a dict. nx.all_shortest_paths(G, s, t)yields every path that ties for shortest.nx.single_source_dijkstra(G, s, weight=...)returns distances and paths together.nx.astar_path(G, s, t, heuristic=h, weight=...)speeds things up on spatial graphs with a good distance estimate.dict(nx.all_pairs_shortest_path_length(G))computes every pair, which is quadratic, so only for small graphs.
If the target can't be reached, shortest_path raises `nx.NetworkXNoPath`; check first with nx.has_path(G, s, t) or catch the exception. A missing node raises nx.NodeNotFound.
In a DiGraph, paths follow edge direction. nx.eccentricity, nx.diameter and nx.average_shortest_path_length summarize distances but require a connected graph.
Example
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([
("A", "B", 4), ("A", "C", 1), ("C", "B", 2), ("B", "D", 5), ("C", "D", 8),
], weight="km")
G.add_node("Z") # unreachable
print(nx.shortest_path(G, "A", "D")) # ['A', 'B', 'D'] (2 hops)
print(nx.shortest_path(G, "A", "D", weight="km")) # ['A', 'C', 'B', 'D']
print(nx.shortest_path_length(G, "A", "D", weight="km")) # 8
dist, paths = nx.single_source_dijkstra(G, "A", weight="km")
print(dist) # {'A': 0, 'C': 1, 'B': 3, 'D': 8}
try:
nx.shortest_path(G, "A", "Z")
except nx.NetworkXNoPath as e:
print("no path:", e) # no path: No path between A and Z.Remember
- Unweighted = BFS (hops);
weight== Dijkstra (non-negative weights) - Unreachable targets raise
NetworkXNoPath; check withhas_path - All-pairs computations are quadratic: small graphs only
Watch out for
- Using Dijkstra-based functions with negative weights; use Bellman-Ford instead.