scipy.sparse.csgraph.

construct_dist_matrix

scipy.sparse.csgraph.construct_dist_matrix(граф, предшественники, направленный=True, null_value=np.inf)

Построить матрицу расстояний из матрицы предшественников

Добавлено в версии 0.11.0.

Параметры:

графarray_like или разреженный

Матричное представление размера N x N направленного или ненаправленного графа. Если плотное, то отсутствующие рёбра обозначаются нулями или бесконечностями.

предшественникиarray_like

Матрица N x N предшественников каждого узла (см. примечания ниже).

направленныйbool, необязательно

Если True (по умолчанию), то работает с ориентированным графом: движение только от точки i к точке j по путям csgraph[i, j]. Если False, то работает с неориентированным графом: алгоритм может переходить от точки i к j по csgraph[i, j] или csgraph[j, i].

null_valuebool, необязательно

значение для расстояний между несвязанными узлами. По умолчанию np.inf

Возвращает:

dist_matrixndarray

Матрица N x N расстояний между узлами вдоль пути, заданного матрицей предшественников. Если путь не существует, расстояние равно нулю.

Примечания

Матрица-предшественник имеет форму, опционально возвращаемую shortest_path. Строка i матрицы предшественников содержит информацию о кратчайших путях из точки i: каждый элемент predecessors[i, j] даёт индекс предыдущего узла на пути из точки i в точку j. Если путь между точками i и j не существует, то predecessors[i, j] = -9999

Следует отметить, что shortest_path по умолчанию возвращает только матрицу расстояний. С return_predecessors=True, возвращает кортеж с матрицей расстояний в качестве первого элемента и массивом предшественников в качестве второго элемента.

Примеры

Попробуйте в вашем браузере!

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

    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.]])

НазадОткрыть во вкладке