Ctrl+K
scipy.sparse.csgraph.

floyd_warshall#

scipy.sparse.csgraph.floyd_warshall(csgraph, directed=True, return_predecessors=False, unweighted=False, overwrite=False)#

使用 Floyd-Warshall 演算法計算最短路徑長度

在版本 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

return_predecessorsbool，選用

若為 True，則傳回大小為 (N, N) 的前導矩陣。

unweightedbool，選用

若為 True，則尋找未加權的距離。也就是說，不是尋找每個點之間權重總和最小化的路徑，而是尋找邊數最小化的路徑。

overwritebool，選用

若為 True，則使用結果覆寫 csgraph。這僅適用於 csgraph 是具有 dtype=float64 的密集、c 順序陣列。

傳回:
dist_matrixndarray

圖形節點之間距離的 N x N 矩陣。dist_matrix[i,j] 給出沿圖形從點 i 到點 j 的最短距離。

predecessorsndarray

僅在 return_predecessors == True 時傳回。前導矩陣為 N x N 大小，可用於重建最短路徑。前導矩陣的第 i 列包含從點 i 出發的最短路徑資訊：每個條目前導矩陣[i, j] 給出從點 i 到點 j 的路徑中前一個節點的索引。如果點 i 和 j 之間不存在路徑，則前導矩陣[i, j] = -9999

引發:
NegativeCycleError

如果圖形中存在負循環

註解

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

範例

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

>>> 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 = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True)
>>> dist_matrix
array([[0., 1., 2., 2.],
       [1., 0., 3., 1.],
       [2., 3., 0., 3.],
       [2., 1., 3., 0.]])
>>> predecessors
array([[-9999,     0,     0,     1],
       [    1, -9999,     0,     1],
       [    2,     0, -9999,     2],
       [    1,     3,     3, -9999]], dtype=int32)
在本頁中