scipy.sparse.csgraph.

johnson

scipy.sparse.csgraph.johnson(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False)

Berechnet die Längen der kürzesten Pfade mithilfe des Johnson-Algorithmus.

Der Johnson-Algorithmus kombiniert den Bellman-Ford-Algorithmus und den Dijkstra-Algorithmus, um schnell die kürzesten Pfade zu finden, und ist robust gegenüber dem Vorhandensein negativer Zyklen. Wenn ein negativer Zyklus erkannt wird, wird ein Fehler ausgelöst. Für Graphen ohne negative Kantengewichte kann Dijkstra schneller sein.

Hinzugefügt in Version 0.11.0.

Parameter:

csgrapharray_like oder Sparse-Array oder Matrix, 2 Dimensionen

Die N x N-Distanzmatrix, die den Eingabegraphen darstellt.

directedbool, optional

Wenn True (Standard), werden die kürzesten Pfade in einem gerichteten Graphen gesucht: nur Bewegung von Punkt i zu Punkt j entlang der Pfade csgraph[i, j]. Wenn False, werden die kürzesten Pfade in einem ungerichteten Graphen gesucht: der Algorithmus kann sich von Punkt i nach j entlang csgraph[i, j] oder csgraph[j, i] bewegen.

indicesarray_like oder int, optional

Wenn angegeben, berechne nur die Pfade von den Punkten an den gegebenen Indizes.

return_predecessorsbool, optional

Wenn True, gib die Vorläufermatrix der Größe (N, N) zurück.

unweightedbool, optional

Wenn True, dann berechne ungewichtete Distanzen. Das heißt, anstatt den Pfad zwischen jedem Punkt zu finden, bei dem die Summe der Gewichte minimiert wird, finde den Pfad, bei dem die Anzahl der Kanten minimiert wird.

Rückgabe:

dist_matrixndarray

Die N x N-Matrix der Distanzen zwischen den Graphenknoten. dist_matrix[i,j] gibt die kürzeste Distanz von Punkt i zu Punkt j entlang des Graphen an.

predecessorsndarray, shape (n_indices, n_nodes,)

Nur zurückgegeben, wenn return_predecessors == True. Wenn indices None ist, dann n_indices = n_nodes und die Form der Matrix wird (n_nodes, n_nodes). Die Vorgängermatrix, die zur Rekonstruktion der kürzesten Pfade verwendet werden kann. Zeile i der Vorgängermatrix enthält Informationen über die kürzesten Pfade von Punkt i: jeder Eintrag predecessors[i, j] gibt den Index des vorherigen Knotens im Pfad von Punkt i zu Punkt j an. Wenn kein Pfad zwischen Punkt i und j existiert, dann predecessors[i, j] = -9999

Löst aus:

NegativeCycleError

falls negative Zyklen im Graphen vorhanden sind

Hinweise

Diese Routine ist speziell für Graphen mit negativen Kantengewichten konzipiert. Wenn alle Kantengewichte positiv sind, ist der Dijkstra-Algorithmus eine bessere Wahl.

Wenn mehrere gültige Lösungen möglich sind, kann die Ausgabe je nach SciPy- und Python-Version variieren.

Beispiele

Probieren Sie es in Ihrem Browser aus!

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import johnson

>>> graph = [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [2, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)
<Compressed Sparse Row sparse array of dtype 'int64'
    with 5 stored elements and shape (4, 4)>
    Coords  Values
    (0, 1)  1
    (0, 2)  2
    (1, 3)  1
    (2, 0)  2
    (2, 3)  3

>>> dist_matrix, predecessors = johnson(csgraph=graph, directed=False, indices=0, return_predecessors=True)
>>> dist_matrix
array([0., 1., 2., 2.])
>>> predecessors
array([-9999,     0,     0,     1], dtype=int32)

ZurückIn Tab öffnen