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
- graph{sparse matrix, ndarray} of shape (n, n)
Adjacency matrix of the graph. Sparse matrix of format LIL is preferred.
- sourceint
Starting node for path.
- cutoffint, default=None
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)]