single_source_shortest_path_length#

single_source_shortest_path_length(G, source, cutoff=None)[source]#

Compute the shortest path lengths from source to all reachable nodes in G.

Parameters:

GNetworkX graph
sourcenode: Starting node for path
cutoffinteger, optional: Depth to stop the search. Only target nodes where the shortest path to this node from the source node contains <= cutoff + 1 nodes will be included in the returned results.

Returns:

lengthsdict: Dict keyed by node to shortest path length from source node.

See also

shortest_path_length: Shortest path length with specifiable source, target, and weight.
single_source_dijkstra_path_length: Shortest weighted path length from source with Dijkstra algorithm.
single_source_bellman_ford_path_length: Shortest weighted path length from source with Bellman-Ford algorithm.

Examples

>>> G = nx.path_graph(5)
>>> length = nx.single_source_shortest_path_length(G, 0)
>>> length[4]
4
>>> for node in sorted(length):
...     print(f"{node}: {length[node]}")
0: 0
1: 1
2: 2
3: 3
4: 4

Only include paths with length less than or equal to the cutoff keyword argument:

>>> length = nx.single_source_shortest_path_length(G, 0, cutoff=2)
>>> for node in sorted(length):
...     print(f"{node}: {length[node]}")
0: 0
1: 1
2: 2
----

Additional backends implement this function

cugraph : GPU-accelerated backend.

graphblas : OpenMP-enabled sparse linear algebra backend.