scipy.sparse.csgraph.

dijkstra

scipy.sparse.csgraph.dijkstra(csgraph, направленный=True, индексы=None, return_predecessors=False, невзвешенный=False, limit=np.inf, min_only=False)

Алгоритм Дейкстры с использованием очереди с приоритетом

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

Параметры:

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

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

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

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

Предупреждение

Обратитесь к примечаниям ниже при использовании с directed=False.

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

если указано, вычислять только пути от точек с заданными индексами.

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

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

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

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

limitfloat, опционально

Максимальное расстояние для расчета, должно быть >= 0. Использование меньшего предела сократит время вычислений, прерывая расчеты между парами, разделенными расстоянием > предела. Для таких пар расстояние будет равно np.inf (т.е., не соединены).

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

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

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

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

Возвращает:

dist_matrixndarray, форма ([n_indices, ]n_nodes,)

Матрица расстояний между узлами графа. Если min_only=False, dist_matrix имеет форму (n_indices, n_nodes) и dist_matrix[i, j] дает кратчайшее расстояние от точки i до точки j по графу. Если min_only=True, dist_matrix имеет форму (n_nodes,) и содержит для данного узла кратчайший путь к этому узлу от любого из узлов в индексах.

предшественникиndarray, форма ([n_indices, ]n_nodes,)

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

источникиndarray, форма (n_nodes,)

Возвращается только если min_only=True и return_predecessors=True. Содержит индекс источника, который имел кратчайший путь к каждой цели. Если путь не существует в пределах лимита, это будет содержать -9999. Значение по переданным индексам будет равно этому индексу (т.е. самый быстрый способ достичь узла i — начать с узла i).

Примечания

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

Кроме того, эта процедура не работает для графов с отрицательными расстояниями. Отрицательные расстояния могут приводить к бесконечным циклам, которые должны обрабатываться специализированными алгоритмами, такими как алгоритм Беллмана-Форда или алгоритм Джонсона.

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

Примеры

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

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

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

>>> dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, indices=0, return_predecessors=True)
>>> dist_matrix
array([0., 1., 2., 2.])
>>> predecessors
array([-9999,     0,     0,     1], dtype=int32)

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