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)
在此页上