scipy.sparse.csgraph.

日元#

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

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

Added in version 1.14.0.

参数:
csgraph数组或稀疏数组，2 维

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

源代码整数

路径起始节点的索引。

下沉整数

路径终点节点的索引。

K整数

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

有向的bool, 可选

如果 True``（默认），则在有向图上找到最短路径：仅沿路径 ``csgraph[i, j] 从点 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。

Raises:
NegativeCycleError:

如果图中存在负权环

注释

Yen’s algorithm 是一种图搜索算法，用于在具有非负边权的图中找到单源 K 条最短无环路径。该算法由 Jin Y. Yen 于 1971 年发表，它使用任何最短路径算法来找到最佳路径，然后继续寻找最佳路径的 K - 1 条偏离路径。

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

如果存在多个有效解决方案，输出可能会因 SciPy 和 Python 版本的不同而有所变化。

参考文献

示例

>>> from scipy.sparse import csr_matrix
>>> 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_matrix(graph)
>>> print(graph)
<Compressed Sparse Row sparse matrix 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)
On this page