single_source_shortest_path#

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

Compute shortest path between source and all other nodes reachable from source.

Parameters:

GNetworkX graph
sourcenode label: 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:

pathsdictionary: Dictionary, keyed by target, of shortest paths.

See also

shortest_path

Notes

The shortest path is not necessarily unique. So there can be multiple paths between the source and each target node, all of which have the same ‘shortest’ length. For each target node, this function returns only one of those paths.

Examples

>>> G = nx.path_graph(5)
>>> nx.single_source_shortest_path(G, 0)
{0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}

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

>>> nx.single_source_shortest_path(G, 0, cutoff=2)
{0: [0], 1: [0, 1], 2: [0, 1, 2]}
----

Additional backends implement this function

cugraph : GPU-accelerated backend.