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数组或稀疏数组，二维

表示输入图的 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 个最佳路径的偏差。

该算法基于 Dijkstra 算法，用于查找每个最短路径。如果图中存在负边，则应用 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)
  (np.int32(0), np.int32(1))        1
  (np.int32(0), np.int32(2))        2
  (np.int32(1), np.int32(3))        1
  (np.int32(2), np.int32(0))        2
  (np.int32(2), np.int32(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)
本页内容