scipy.sparse.csgraph.

bellman_ford

scipy.sparse.csgraph.bellman_ford(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 bellman_ford

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

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