Ctrl+K
scipy.sparse.csgraph.

yen#

scipy.sparse.csgraph.yen(csgraph, source, sink, K, *, directed=True, return_predecessors=False, unweighted=False)#

在有向或无向图上使用 Yen 的 K-最短路径算法。

在版本 1.14.0 中添加。

参数:
csgraph类数组，或稀疏数组或矩阵，2 维

表示输入图的 N x N 距离数组。

sourceint

路径的起始节点的索引。

sinkint

路径的结束节点的索引。

Kint

要查找的最短路径的数量。

directedbool，可选

如果 True （默认），则在有向图上查找最短路径：仅沿路径 csgraph[i, j] 从点 i 移动到点 j。如果为 False，则在无向图上查找最短路径：算法可以沿 csgraph[i, j] 或 csgraph[j, i] 从点 i 前进到 j。

return_predecessorsbool，可选

如果 True，则返回大小为 (M, N) 的前驱矩阵。默认值：False。

unweightedbool，可选

如果 True，则查找未加权的距离。也就是说，不是查找每个点之间的路径，使得权重之和最小化，而是查找使得边数最小化的路径。默认值：False。

返回:
dist_arrayndarray

大小为 M 的数组，表示源节点和目标节点之间的最短距离。dist_array[i] 给出从源到目标沿图的第 i 个最短距离。M 是找到的最短路径数，小于或等于 K。

predecessorsndarray

仅当 return_predecessors == True 时返回。M x N 前驱矩阵，可用于重建最短路径。M 是找到的最短路径数，小于或等于 K。前驱矩阵的第 i 行包含有关从源到目标的第 i 个最短路径的信息：每个条目 predecessors[i, j] 给出从源到节点 j 的路径中上一个节点的索引。如果路径不通过节点 j，则 predecessors[i, j] = -9999。

引发:
NegativeCycleError

如果图中存在负环

注释

Yen 算法是一种图搜索算法，用于查找具有非负边成本的图的单源 K-最短无环路径。该算法由 Jin Y. Yen 于 1971 年发表，它采用任何最短路径算法来查找最佳路径，然后继续查找最佳路径的 K - 1 个偏差。

该算法基于 Dijsktra 算法来查找每个最短路径。如果图中存在负边，则应用 Johnson 算法。

如果存在多个有效解决方案，则输出可能因 SciPy 和 Python 版本而异。

参考

示例

>>> 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)
<Compressed Sparse Row sparse array of dtype 'int64'
    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)
在此页上