single_target_shortest_path

single_target_shortest_path(G, target, cutoff=None)

Compute shortest path to target from all nodes that reach target.

Parameters:

GNetworkX graph

targetnode label

Target node for path

cutoffinteger, optional

Depth to stop the search. Only source nodes where the shortest path from this node to the target node contains <= cutoff + 1 nodes will be included in the returned results.

Returns:

pathsdictionary

Dictionary, keyed by source, of shortest paths.

See also

shortest_path, single_source_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, create_using=nx.DiGraph())
>>> nx.single_target_shortest_path(G, 4)
{4: [4], 3: [3, 4], 2: [2, 3, 4], 1: [1, 2, 3, 4], 0: [0, 1, 2, 3, 4]}

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

>>> nx.single_target_shortest_path(G, 4, cutoff=2)
{4: [4], 3: [3, 4], 2: [2, 3, 4]}
----

Additional backends implement this function

cugraph : GPU-accelerated backend.