scipy.sparse.csgraph.

bellman_ford

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

Berechnet die kürzesten Pfadlängen mit dem Bellman-Ford-Algorithmus.

Der Bellman-Ford-Algorithmus kann robust mit Graphen mit negativen Gewichten umgehen. Wenn ein negativer Zyklus erkannt wird, wird ein Fehler ausgelöst. Für Graphen ohne negative Kantengewichte kann der Dijkstra-Algorithmus 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 ist n_indices = n_nodes und die Form der Matrix wird (n_nodes, n_nodes). Die Matrix der Vorgänger, 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 ist 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 ausgelegt. Wenn alle Kantengewichte positiv sind, ist der Dijkstra-Algorithmus die 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 bellman_ford

>>> 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 = bellman_ford(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