scipy.sparse.csgraph.

johnson#

scipy.sparse.csgraph.johnson(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False)#

使用 Johnson 演算法計算最短路徑長度。

Johnson 演算法結合了 Bellman-Ford 演算法和 Dijkstra 演算法，以快速找到最短路徑，並且能夠有效地處理負循環。如果偵測到負循環，則會引發錯誤。對於沒有負邊權重的圖形，dijkstra 可能會更快。

在 0.11.0 版本中新增。

參數:

csgrapharray_like，或稀疏陣列或矩陣，2 維度: 代表輸入圖形的 N x N 距離陣列。
directedbool，選用: 如果為 True（預設），則在有向圖上尋找最短路徑：僅沿著路徑 csgraph[i, j] 從點 i 移動到點 j。如果為 False，則在無向圖上尋找最短路徑：演算法可以沿著 csgraph[i, j] 或 csgraph[j, i] 從點 i 進行到點 j
indicesarray_like 或 int，選用: 如果指定，則僅計算從給定索引點的路徑。
return_predecessorsbool，選用: 如果為 True，則傳回大小為 (N, N) 的前趨矩陣。
unweightedbool，選用: 如果為 True，則尋找未加權的距離。也就是說，不是找到每個點之間權重總和最小化的路徑，而是找到邊數最小化的路徑。

傳回:

dist_matrixndarray: 圖形節點之間的 N x N 距離矩陣。dist_matrix[i,j] 給出從點 i 到點 j 沿圖形的最短距離。
predecessorsndarray: 僅在 return_predecessors == True 時傳回。可以用於重建最短路徑的 N x N 前趨矩陣。前趨矩陣的第 i 列包含從點 i 出發的最短路徑資訊：每個條目 predecessors[i, j] 給出從點 i 到點 j 的路徑中前一個節點的索引。如果點 i 和 j 之間不存在路徑，則 predecessors[i, j] = -9999

引發:

NegativeCycleError: 如果圖形中存在負循環

註解

此常式專為具有負邊權重的圖形設計。如果所有邊權重都為正數，則 Dijkstra 演算法是更好的選擇。

如果存在多個有效的解決方案，則輸出可能因 SciPy 和 Python 版本而異。

範例

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import johnson

>>> 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_matrix, predecessors = johnson(csgraph=graph, directed=False, indices=0, return_predecessors=True)
>>> dist_matrix
array([0., 1., 2., 2.])
>>> predecessors
array([-9999,     0,     0,     1], dtype=int32)