single_source_shortest_path_length

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

Gibt die Länge des kürzesten Pfades von der Quelle zu allen erreichbaren Knoten zurück.

Parameter:

graph{array-like, sparse matrix} der Form (n_nodes, n_nodes)

Adjazenzmatrix des Graphen. Sparse-Matrix im LIL-Format wird bevorzugt.

sourceint

Startknoten für den Pfad.

cutoffint, default=None

Tiefe, bis zu der die Suche durchgeführt wird – nur Pfade mit Längen <= cutoff werden zurückgegeben.

Gibt zurück:

pathsdict

Erreichbare Endknoten, abgebildet auf die Länge des Pfades vom Quellknoten, d.h. {end: path_length}.

Beispiele

>>> 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, 0],
...                   [ 0, 0, 0, 0]])
>>> single_source_shortest_path_length(graph, 0)
{0: 0, 1: 1, 2: 2}
>>> graph = np.ones((6, 6))
>>> sorted(single_source_shortest_path_length(graph, 2).items())
[(0, 1), (1, 1), (2, 0), (3, 1), (4, 1), (5, 1)]