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類陣列 (array_like)，或稀疏陣列或矩陣，2 維度

代表輸入圖的 N x N 距離陣列。

source (來源)int

路徑起點節點的索引。

sink (終點)int

路徑終點節點的索引。

Kint

要尋找的最短路徑數量。

directed (有向)bool, optional

如果為 True (預設)，則在有向圖上尋找最短路徑：僅沿著路徑 csgraph[i, j] 從點 i 移動到點 j。如果為 False，則在無向圖上尋找最短路徑：演算法可以沿著 csgraph[i, j] 或 csgraph[j, i] 從點 i 進行到點 j。

return_predecessors (返回前導節點)bool, optional

如果為 True，則返回大小為 (M, N) 的前導節點矩陣。預設值：False。

unweighted (無權重)bool, optional

如果為 True，則尋找無權重距離。也就是說，不是尋找每個點之間權重總和最小化的路徑，而是尋找邊數最小化的路徑。預設值：False。

返回:
dist_array (距離陣列)ndarray

大小為 M 的陣列，包含來源節點和終點節點之間的最短距離。dist_array[i] 給出圖形上從來源到終點的第 i 條最短距離。M 是找到的最短路徑數量，小於或等於 K。

predecessors (前導節點)ndarray

僅在 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_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)
在本頁面上