scipy.sparse.csgraph.

floyd_warshall

scipy.sparse.csgraph.floyd_warshall(csgraph, directed=True, return_predecessors=False, unweighted=False, overwrite=False)

Berechnet die kürzesten Pfadlängen mit dem Floyd-Warshall-Algorithmus

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.

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.

overwritebool, optional

Wenn True, wird csgraph mit dem Ergebnis überschrieben. Dies gilt nur, wenn csgraph ein dichter, C-orientierter Array mit dtype=float64 ist.

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

Nur zurückgegeben, wenn return_predecessors == True. Die N x N-Matrix der Vorgänger, die zum Wiederherstellen 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 ist predecessors[i, j] = -9999

Löst aus:

NegativeCycleError

falls negative Zyklen im Graphen vorhanden sind

Hinweise

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 floyd_warshall

>>> 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 = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True)
>>> dist_matrix
array([[0., 1., 2., 2.],
       [1., 0., 3., 1.],
       [2., 3., 0., 3.],
       [2., 1., 3., 0.]])
>>> predecessors
array([[-9999,     0,     0,     1],
       [    1, -9999,     0,     1],
       [    2,     0, -9999,     2],
       [    1,     3,     3, -9999]], dtype=int32)

ZurückIn Tab öffnen