scipy.sparse.csgraph.

dijkstra

scipy.sparse.csgraph.dijkstra(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False, limit=np.inf, min_only=False)

Dijkstra-Algorithmus mit Prioritätswarteschlange

Hinzugefügt in Version 0.11.0.

Parameter:

csgrapharray_like oder Sparse-Array oder Matrix, 2 Dimensionen

Das N x N-Array von nicht-negativen Distanzen, das den Eingabegraphen darstellt.

directedbool, optional

Wenn True (Standard), dann finde den kürzesten Pfad in einem gerichteten Graphen: bewege dich nur von Punkt i zu Punkt j entlang der Pfade csgraph[i, j] und von Punkt j zu i entlang der Pfade csgraph[j, i]. Wenn False, dann finde den kürzesten Pfad in einem ungerichteten Graphen: der Algorithmus kann sich von Punkt i zu j oder j zu i entlang entweder csgraph[i, j] oder csgraph[j, i] bewegen.

Warnung

Beachte die untenstehenden Hinweise bei der Verwendung von directed=False.

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.

limitfloat, optional

Die maximal zu berechnende Distanz, muss >= 0 sein. Die Verwendung eines kleineren Limits verringert die Rechenzeit, indem Berechnungen zwischen Paaren abgebrochen werden, die durch eine Distanz > limit getrennt sind. Für solche Paare ist die Distanz gleich np.inf (d.h. nicht verbunden).

Hinzugefügt in Version 0.14.0.

min_onlybool, optional

Wenn False (Standard), finde für jeden Knoten im Graphen den kürzesten Pfad von jedem Knoten in indices. Wenn True, finde für jeden Knoten im Graphen den kürzesten Pfad von einem der Knoten in indices (was erheblich schneller sein kann).

Hinzugefügt in Version 1.3.0.

Rückgabe:

dist_matrixndarray, shape ([n_indices, ]n_nodes,)

Die Matrix der Distanzen zwischen den Graphenknoten. Wenn min_only=False, hat dist_matrix die Form (n_indices, n_nodes) und dist_matrix[i, j] gibt die kürzeste Distanz von Punkt i zu Punkt j entlang des Graphen an. Wenn min_only=True, hat dist_matrix die Form (n_nodes,) und enthält für einen gegebenen Knoten den kürzesten Pfad zu diesem Knoten von einem der Knoten in indices.

predecessorsndarray, shape ([n_indices, ]n_nodes,)

Wenn min_only=False, hat dies die Form (n_indices, n_nodes), andernfalls hat es die Form (n_nodes,). Wenn indices None ist und min_only=False, dann ist n_indices = n_nodes und die Form der Matrix wird (n_nodes, n_nodes). Wird nur zurückgegeben, wenn return_predecessors == True. Die Vorläufermatrix, die zur Rekonstruktion der kürzesten Pfade verwendet werden kann. Zeile i der Vorläufermatrix enthält Informationen über die kürzesten Pfade von Punkt i: jeder Eintrag predecessors[i, j] gibt den Index des vorherigen Knotens auf dem Pfad von Punkt i zu Punkt j an. Wenn kein Pfad zwischen Punkt i und j existiert, dann ist predecessors[i, j] = -9999

sourcesndarray, shape (n_nodes,)

Wird nur zurückgegeben, wenn min_only=True und return_predecessors=True. Enthält den Index der Quelle, die den kürzesten Pfad zu jedem Ziel hatte. Wenn kein Pfad innerhalb des Limits existiert, wird hier -9999 stehen. Der Wert an den übergebenen Indizes wird gleich diesem Index sein (d.h. der schnellste Weg, Knoten i zu erreichen, ist, bei Knoten i zu starten).

Hinweise

In der aktuellen Implementierung funktioniert der Dijkstra-Algorithmus nicht für Graphen mit richtungsabhängigen Distanzen, wenn directed == False. Das heißt, wenn csgraph[i,j] und csgraph[j,i] nicht gleich und beide ungleich Null sind, liefert das Setzen von directed=False kein korrektes Ergebnis.

Außerdem funktioniert diese Routine nicht für Graphen mit negativen Distanzen. Negative Distanzen können zu unendlichen Zyklen führen, die von spezialisierten Algorithmen wie dem Bellman-Ford-Algorithmus oder dem Johnson-Algorithmus behandelt werden müssen.

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 dijkstra

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

>>> dist_matrix, predecessors = dijkstra(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