scipy.sparse.csgraph.

йена

scipy.sparse.csgraph.йена(csgraph, источник, сток, K, *, направленный=True, return_predecessors=False, невзвешенный=False)

Алгоритм K-кратчайших путей Йена на ориентированном или неориентированном графе.

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

Параметры:

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

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

источникint

Индекс начального узла для путей.

стокint

Индекс конечного узла для путей.

Kint

Количество кратчайших путей для поиска.

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

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

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

Если True, вернуть размер (M, N) матрица предшественников. По умолчанию: False.

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

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

Возвращает:

dist_arrayndarray

Массив размера M кратчайших расстояний между исходным и конечным узлами. dist_array[i] дает i-е кратчайшее расстояние от источника к стоку вдоль графа. M — это количество найденных кратчайших путей, которое меньше или равно K.

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

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

Вызывает:

NegativeCycleError:

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

Примечания

Алгоритм Йена — это алгоритм поиска в графе, который находит кратчайшие пути из одной вершины K-кратчайшие пути без циклов для графа с неотрицательной стоимостью рёбер. Алгоритм был опубликован Джином Й. Йеном в 1971 году и использует любой алгоритм поиска кратчайшего пути для нахождения наилучшего пути, затем продолжает находить K - 1 отклонения лучшего пути.

Алгоритм основан на алгоритме Дейкстры для нахождения каждого кратчайшего пути. В случае наличия отрицательных рёбер в графе применяется алгоритм Джонсона.

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

Ссылки

[1]

https://en.wikipedia.org/wiki/Yen%27s_algorithm

[2]

https://www.ams.org/journals/qam/1970-27-04/S0033-569X-1970-0253822-7/

Примеры

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

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

>>> 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_array, predecessors = yen(csgraph=graph, source=0, sink=3, K=2,
...                                directed=False, return_predecessors=True)
>>> dist_array
array([2., 5.])
>>> predecessors
array([[-9999,     0, -9999,     1],
    [-9999, -9999,     0,     2]], dtype=int32)

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