scipy.sparse.csgraph.

johnson#

scipy.sparse.csgraph.johnson(csgraph, направленный=True, индексы=None, return_predecessors=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]
индексыarray_like или int, опционально: если указано, вычислять только пути от точек с заданными индексами.
return_predecessorsbool, необязательно: Если True, возвращает матрицу предшественников размера (N, N).
невзвешенныйbool, необязательно: Если True, то находить невзвешенные расстояния. То есть вместо нахождения пути между каждой точкой, минимизирующего сумму весов, находить путь, минимизирующий количество рёбер.

Возвращает:

dist_matrixndarray: Матрица N x N расстояний между узлами графа. dist_matrix[i,j] даёт кратчайшее расстояние от точки i до точки j вдоль графа.
предшественникиndarray, форма (n_indices, n_nodes,): Возвращается только если return_predecessors == True. Если индексы равно None, тогда n_indices = n_nodes и форма матрицы становится (n_nodes, n_nodes). Матрица предшественников, которую можно использовать для восстановления кратчайших путей. Строка 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 johnson

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