scipy.sparse.csgraph.

shortest_path#

scipy.sparse.csgraph.shortest_path(csgraph, метод='auto', направленный=True, return_predecessors=False, невзвешенный=False, перезаписать=False, индексы=None)#

Выполнить поиск кратчайшего пути в ориентированном или неориентированном графе с положительными весами.

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

Параметры:

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

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

методстрока [‘auto’|’FW’|’D’], опционально

Алгоритм для использования кратчайших путей. Варианты:

‘auto’ – (по умолчанию) выбрать лучшее среди ‘FW’, ‘D’, ‘BF’ или ‘J’
на основе входных данных.

‘FW’ — алгоритм Флойда-Уоршелла.
Вычислительная стоимость составляет приблизительно O[N^3]. Входной csgraph будет преобразован в плотное представление.

‘D’ – алгоритм Дейкстры с очередью с приоритетом.
Вычислительная стоимость составляет приблизительно O[I * (E + N) * log(N)], где E это количество ребер в графе, I = len(indices) if indices передается. В противном случае, I = N. Входной csgraph будет преобразован в представление csr.

‘BF’ – алгоритм Беллмана-Форда.
Этот алгоритм можно использовать, когда веса отрицательные. Если встретится отрицательный цикл, будет вызвана ошибка. Вычислительная стоимость составляет примерно O[N(N^2 k)], где k является средним количеством связанных ребер на узел. Входной csgraph будет преобразован в csr представление.

‘J’ – алгоритм Джонсона.
Как и алгоритм Беллмана-Форда, алгоритм Джонсона предназначен для использования, когда веса отрицательны. Он сочетает алгоритм Беллмана-Форда с алгоритмом Дейкстры для более быстрого вычисления.

направленный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 результатом. Это применяется только если method == 'FW' и csgraph — плотный массив с порядком C и dtype=float64.

индексыarray_like или int, опционально

Если указано, вычислять только пути от точек с заданными индексами. Несовместимо с method == 'FW'.

Возвращает:

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:: если в графе есть отрицательные циклы

Смотрите также

Пример: Word Ladders: Иллюстрация shortest_path API с осмысленным примером. Также восстанавливает кратчайший путь с использованием матрицы предшественников, возвращаемой этой функцией.

Примечания

В текущей реализации алгоритм Дейкстры и алгоритм Джонсона не работают для графов с расстояниями, зависящими от направления, когда directed == False. Т.е., если csgraph[i,j] и csgraph[j,i] — неравные ребра, метод='D' может дать неверный результат.

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

Примеры

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

>>> graph = [
... [0, 0, 7, 0],
... [0, 0, 8, 5],
... [7, 8, 0, 0],
... [0, 5, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)

    with 6 stored elements and shape (4, 4)>
    Coords  Values
    (0, 2)  7
    (1, 2)  8
    (1, 3)  5
    (2, 0)  7
    (2, 1)  8
    (3, 1)  5

>>> sources = [0, 2]
>>> dist_matrix, predecessors = shortest_path(csgraph=graph, directed=False, indices=sources, return_predecessors=True)
>>> dist_matrix
array([[ 0., 15.,  7., 20.],
       [ 7.,  8.,  0., 13.]])
>>> predecessors
array([[-9999,     2,     0,     1],
       [    2,     2, -9999,     1]], dtype=int32)

Восстановление кратчайших путей от источников ко всем узлам графа.

>>> shortest_paths = {}
>>> for idx in range(len(sources)):
...     for node in range(4):
...         curr_node = node # start from the destination node
...         path = []
...         while curr_node != -9999: # no previous node available, exit the loop
...             path = [curr_node] + path # prefix the previous node obtained from the last iteration
...             curr_node = int(predecessors[idx][curr_node]) # set current node to previous node
...         shortest_paths[(sources[idx], node)] = path
...

Вычисление длины кратчайшего пути от узла 0 к узлу 3 графа. Можно заметить, что вычисленная длина и dist_matrix значения точно одинаковы.

>>> shortest_paths[(0, 3)]
[0, 2, 1, 3]
>>> path03 = shortest_paths[(0, 3)]
>>> sum([graph[path03[0], path03[1]], graph[path03[1], path03[2]], graph[path03[2], path03[3]]])
np.int64(20)
>>> dist_matrix[0][3]
np.float64(20.0)

Еще один пример вычисления длины кратчайшего пути от узла 2 к узлу 3. Здесь, dist_matrix[1][3] используется для получения длины пути, возвращаемого shortest_path. Это потому, что узел 2 является вторым источником, поэтому длины пути от него к другим узлам в графе будут находиться по индексу 1 в dist_matrix.

>>> shortest_paths[(2, 3)]
[2, 1, 3]
>>> path23 = shortest_paths[(2, 3)]
>>> sum([graph[path23[0], path23[1]], graph[path23[1], path23[2]]])
np.int64(13)
>>> dist_matrix[1][3]
np.float64(13.0)