scipy.sparse.csgraph.

yen#

scipy.sparse.csgraph.yen(csgraph, source, sink, K, *, directed=True, return_predecessors=False, unweighted=False)#

Yen's K-Shortest Paths Algorithmus auf einem gerichteten oder ungerichteten Graphen.

Hinzugefügt in Version 1.14.0.

Parameter:
csgrapharray_like oder Sparse-Array oder Matrix, 2 Dimensionen

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

sourceint

Der Index des Startknotens für die Pfade.

sinkint

Der Index des Endknotens für die Pfade.

Kint

Die Anzahl der zu findenden kürzesten Pfade.

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]. Wenn False, dann finde den kürzesten Pfad in einem ungerichteten Graphen: 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 Größe (M, N) der Vorgängermatrix zurück. Standard: False.

unweightedbool, optional

Wenn True, dann finde ungewichtete Distanzen. Das heißt, anstatt den Pfad zwischen jedem Punkt zu finden, dessen Gewichtssumme minimiert wird, finde den Pfad, dessen Kantenanzahl minimiert wird. Standard: False.

Rückgabe:
dist_arrayndarray

Array der Größe M der kürzesten Distanzen zwischen den Quell- und Zielknoten. dist_array[i] gibt die i-te kürzeste Distanz vom Quellknoten zum Zielknoten entlang des Graphen an. M ist die Anzahl der gefundenen kürzesten Pfade, die kleiner oder gleich K ist.

predecessorsndarray

Nur zurückgegeben, wenn return_predecessors == True. Die M x N Matrix der Vorgänger, die zur Rekonstruktion der kürzesten Pfade verwendet werden kann. M ist die Anzahl der gefundenen kürzesten Pfade, die kleiner oder gleich K ist. Zeile i der Vorgängermatrix enthält Informationen über den i-ten kürzesten Pfad vom Quellknoten zum Zielknoten: jeder Eintrag predecessors[i, j] gibt den Index des vorhergehenden Knotens im Pfad vom Quellknoten zum Knoten j an. Wenn der Pfad nicht über den Knoten j verläuft, dann ist predecessors[i, j] = -9999.

Löst aus:
NegativeCycleError

Wenn es negative Zyklen im Graphen gibt

Hinweise

Yen's Algorithmus ist ein Graph-Suchalgorithmus, der einzelne Quell- K-kürzeste Pfade ohne Schleifen für einen Graphen mit nicht-negativen Kantengewichten findet. Der Algorithmus wurde 1971 von Jin Y. Yen veröffentlicht und verwendet einen beliebigen Algorithmus für kürzeste Pfade, um den besten Pfad zu finden, und fährt dann fort, K - 1 Abweichungen vom besten Pfad zu finden.

Der Algorithmus basiert auf Dijkstra's Algorithmus zum Finden jedes kürzesten Pfades. Falls negative Kanten im Graphen vorhanden sind, wird Johnsons Algorithmus angewendet.

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

Referenzen

Beispiele

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

>>> 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_array, predecessors = yen(csgraph=graph, source=0, sink=3, K=2,
...                                directed=False, return_predecessors=True)
>>> dist_array
array([2., 5.])
>>> predecessors
array([[-9999,     0, -9999,     1],
    [-9999, -9999,     0,     2]], dtype=int32)
Auf dieser Seite