sklearn.utils.graph.single_source_shortest_path_length¶

sklearn.utils.graph.single_source_shortest_path_length(graph, source, *, cutoff=None)[source]¶

Return the shortest path length from source to all reachable nodes.

Returns a dictionary of shortest path lengths keyed by target.

Parameters

graphsparse matrix or 2D array (preferably LIL matrix)

Adjacency matrix of the graph

sourceinteger

Starting node for path

cutoffinteger, optional

Depth to stop the search - only paths of length <= cutoff are returned.

Examples

>>> from sklearn.utils.graph import single_source_shortest_path_length
>>> import numpy as np
>>> graph = np.array([[ 0, 1, 0, 0],
...                   [ 1, 0, 1, 0],
...                   [ 0, 1, 0, 1],
...                   [ 0, 0, 1, 0]])
>>> list(sorted(single_source_shortest_path_length(graph, 0).items()))
[(0, 0), (1, 1), (2, 2), (3, 3)]
>>> graph = np.ones((6, 6))
>>> list(sorted(single_source_shortest_path_length(graph, 2).items()))
[(0, 1), (1, 1), (2, 0), (3, 1), (4, 1), (5, 1)]