scipy.sparse.csgraph.

construct_dist_matrix#

scipy.sparse.csgraph.construct_dist_matrix(graph, predecessors, directed=True, null_value=np.inf)#

Konstruiere Distanzmatrix aus einer Vorgängermatrix

Hinzugefügt in Version 0.11.0.

Parameter:

grapharray_like oder sparse: Die N x N Matrixdarstellung eines gerichteten oder ungerichteten Graphen. Wenn dicht, dann werden Nicht-Kanten durch Nullen oder Unendlichkeiten angezeigt.
predecessorsarray_like: Die N x N Matrix der Vorgänger jedes Knotens (siehe Hinweise unten).
directedbool, optional: Wenn True (Standard), dann auf einem gerichteten Graphen operieren: nur von Punkt i zu Punkt j entlang der Pfade csgraph[i, j] bewegen. Wenn False, dann auf einem ungerichteten Graphen operieren: der Algorithmus kann sich von Punkt i nach j entlang csgraph[i, j] oder csgraph[j, i] bewegen.
null_valuebool, optional: Wert, der für Distanzen zwischen nicht verbundenen Knoten verwendet werden soll. Standard ist np.inf

Rückgabe:

dist_matrixndarray: Die N x N Matrix der Distanzen zwischen Knoten entlang des Pfades, der durch die Vorgängermatrix spezifiziert ist. Wenn kein Pfad existiert, ist die Distanz Null.

Hinweise

Die Vorgängermatrix hat die Form, die optional von shortest_path zurückgegeben wird. 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

Es ist zu beachten, dass shortest_path standardmäßig nur die Distanzmatrix zurückgibt. Mit return_predecessors=True gibt sie ein Tupel mit der Distanzmatrix als erstes Element und der Vorgänger-Array als zweites Element zurück.

Beispiele

>>> import numpy as np
>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import construct_dist_matrix

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

>>> pred = np.array([[-9999, 0, 0, 2],
...                  [1, -9999, 0, 1],
...                  [2, 0, -9999, 2],
...                  [1, 3, 3, -9999]], dtype=np.int32)

>>> construct_dist_matrix(graph=graph, predecessors=pred, directed=False)
array([[0., 1., 2., 5.],
       [1., 0., 3., 1.],
       [2., 3., 0., 3.],
       [2., 1., 3., 0.]])