scipy.sparse.csgraph.

floyd_warshall

scipy.sparse.csgraph.floyd_warshall(csgraph, направленный=True, return_predecessors=False, невзвешенный=False, перезаписать=False)

Вычислить длины кратчайших путей с использованием алгоритма Флойда-Уоршелла

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

Параметры:

csgrapharray_like, или разреженный массив или матрица, 2 измерения

Массив расстояний размером N x N, представляющий входной граф.

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

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

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

Если True, возвращает матрицу предшественников размера (N, N).

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

Если True, то находить невзвешенные расстояния. То есть вместо нахождения пути между каждой точкой, минимизирующего сумму весов, находить путь, минимизирующий количество рёбер.

перезаписатьbool, необязательно

Если True, перезаписать csgraph результатом. Применяется только если csgraph является плотным массивом с порядком C и dtype=float64.

Возвращает:

dist_matrixndarray

Матрица N x N расстояний между узлами графа. dist_matrix[i,j] даёт кратчайшее расстояние от точки i до точки j вдоль графа.

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

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

Вызывает:

NegativeCycleError:

если в графе есть отрицательные циклы

Примечания

Если возможны несколько допустимых решений, вывод может варьироваться в зависимости от версии SciPy и Python.

Примеры

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

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

>>> graph = [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [2, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)

    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_matrix, predecessors = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True)
>>> dist_matrix
array([[0., 1., 2., 2.],
       [1., 0., 3., 1.],
       [2., 3., 0., 3.],
       [2., 1., 3., 0.]])
>>> predecessors
array([[-9999,     0,     0,     1],
       [    1, -9999,     0,     1],
       [    2,     0, -9999,     2],
       [    1,     3,     3, -9999]], dtype=int32)

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