scipy.sparse.csgraph.

shortest_path

scipy.sparse.csgraph.shortest_path(csgraph, method='auto', directed=True, return_predecessors=False, unweighted=False, overwrite=False, indices=None)

Führt eine kürzeste-Pfad-Graph-Suche auf einem positiven gerichteten oder ungerichteten Graphen durch.

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.

methodstring [‘auto’|’FW’|’D’], optional

Algorithmus zur Bestimmung der kürzesten Pfade. Optionen sind:

‘auto’ – (Standard) wählt den besten aus ‘FW’, ‘D’, ‘BF’ oder ‘J’

basierend auf den Eingabedaten.

‘FW’ – Floyd-Warshall-Algorithmus.

Die Berechnungskosten betragen ungefähr O[N^3]. Der Eingabegraph wird in eine dichte Darstellung konvertiert.

‘D’ – Dijkstra-Algorithmus mit Prioritätswarteschlange.

Die Berechnungskosten betragen ungefähr O[I * (E + N) * log(N)], wobei E die Anzahl der Kanten im Graphen ist und I = len(indices) ist, wenn indices übergeben wird. Andernfalls ist I = N. Der Eingabegraph wird in eine CSR-Darstellung konvertiert.

‘BF’ – Bellman-Ford-Algorithmus.

Dieser Algorithmus kann verwendet werden, wenn Gewichte negativ sind. Wenn ein negativer Zyklus erkannt wird, wird ein Fehler ausgelöst. Die Berechnungskosten betragen ungefähr O[N(N^2 k)], wobei k die durchschnittliche Anzahl verbundener Kanten pro Knoten ist. Der Eingabegraph wird in eine CSR-Darstellung konvertiert.

‘J’ – Johnsons Algorithmus.

Ähnlich wie der Bellman-Ford-Algorithmus ist Johnsons Algorithmus für die Verwendung bei negativen Gewichten konzipiert. Er kombiniert den Bellman-Ford-Algorithmus mit dem Dijkstra-Algorithmus für eine schnellere Berechnung.

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 der csgraph mit dem Ergebnis überschrieben. Dies gilt nur, wenn method == ‘FW’ und csgraph ein dichtes, c-geordnetes Array mit dtype=float64 ist.

indicesarray_like oder int, optional

Wenn angegeben, werden nur die Pfade von den Punkten an den gegebenen Indizes berechnet. Inkompatibel mit method == ‘FW’.

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,)

Wird 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 ist predecessors[i, j] = -9999.

Löst aus:

NegativeCycleError

falls negative Zyklen im Graphen vorhanden sind

Siehe auch

Beispiel: Wortleitern

Eine Veranschaulichung der shortest_path API mit einem aussagekräftigen Beispiel. Es rekonstruiert auch den kürzesten Pfad unter Verwendung der von dieser Funktion zurückgegebenen Vorgängermatrix.

Hinweise

Wie derzeit implementiert, funktionieren der Dijkstra-Algorithmus und der Johnson-Algorithmus nicht für Graphen mit richtungsabhängigen Distanzen, wenn directed == False. D. h., wenn csgraph[i,j] und csgraph[j,i] ungleiche Kanten sind, kann method=’D’ zu einem falschen Ergebnis führen.

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 shortest_path

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

>>> sources = [0, 2]
>>> dist_matrix, predecessors = shortest_path(csgraph=graph, directed=False, indices=sources, return_predecessors=True)
>>> dist_matrix
array([[ 0., 15.,  7., 20.],
       [ 7.,  8.,  0., 13.]])
>>> predecessors
array([[-9999,     2,     0,     1],
       [    2,     2, -9999,     1]], dtype=int32)

Rekonstruktion kürzester Pfade von Quellen zu allen Knoten des Graphen.

>>> shortest_paths = {}
>>> for idx in range(len(sources)):
...     for node in range(4):
...         curr_node = node # start from the destination node
...         path = []
...         while curr_node != -9999: # no previous node available, exit the loop
...             path = [curr_node] + path # prefix the previous node obtained from the last iteration
...             curr_node = int(predecessors[idx][curr_node]) # set current node to previous node
...         shortest_paths[(sources[idx], node)] = path
...

Berechnung der Länge des kürzesten Pfades von Knoten 0 zu Knoten 3 des Graphen. Es ist zu beobachten, dass die berechnete Länge und der Wert von dist_matrix genau gleich sind.

>>> shortest_paths[(0, 3)]
[0, 2, 1, 3]
>>> path03 = shortest_paths[(0, 3)]
>>> sum([graph[path03[0], path03[1]], graph[path03[1], path03[2]], graph[path03[2], path03[3]]])
np.int64(20)
>>> dist_matrix[0][3]
np.float64(20.0)

Ein weiteres Beispiel für die Berechnung der kürzesten Pfadlänge von Knoten 2 zu Knoten 3. Hier wird dist_matrix[1][3] verwendet, um die Länge des von shortest_path zurückgegebenen Pfades zu erhalten. Dies liegt daran, dass Knoten 2 die zweite Quelle ist, sodass die Längen des Pfades von ihr zu anderen Knoten im Graphen im Index 1 in dist_matrix stehen.

>>> shortest_paths[(2, 3)]
[2, 1, 3]
>>> path23 = shortest_paths[(2, 3)]
>>> sum([graph[path23[0], path23[1]], graph[path23[1], path23[2]]])
np.int64(13)
>>> dist_matrix[1][3]
np.float64(13.0)

ZurückIn Tab öffnen