Ctrl+K
scipy.sparse.csgraph.

shortest_path#

scipy.sparse.csgraph.shortest_path(csgraph, method='auto', directed=True, return_predecessors=False, unweighted=False, overwrite=False, indices=None)#

在正向有向或無向圖上執行最短路徑圖搜尋。

在 0.11.0 版本中新增。

參數:
csgrapharray_like，或稀疏陣列或矩陣，2 維

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

method字串 [‘auto’|’FW’|’D’]，選用

用於最短路徑的演算法。選項為

‘auto’ – (預設) 根據輸入資料選擇 ‘FW’、‘D’、‘BF’ 或 ‘J’ 中最佳的。

基於輸入資料。

‘FW’ – Floyd-Warshall 演算法。

計算成本約為 O[N^3]。輸入 csgraph 將轉換為密集表示法。

‘D’ – Dijkstra 演算法搭配費氏堆積。

計算成本約為 O[N(N*k + N*log(N))]，其中 k 是每個節點的平均連接邊數。輸入 csgraph 將轉換為 csr 表示法。

‘BF’ – Bellman-Ford 演算法。

當權重為負數時，可以使用此演算法。如果遇到負環，將會引發錯誤。計算成本約為 O[N(N^2 k)]，其中 k 是每個節點的平均連接邊數。輸入 csgraph 將轉換為 csr 表示法。

‘J’ – Johnson 演算法。

與 Bellman-Ford 演算法類似，Johnson 演算法設計用於權重為負數的情況。它結合了 Bellman-Ford 演算法和 Dijkstra 演算法，以實現更快的計算速度。

directed布林值，選用

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

return_predecessors布林值，選用

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

unweighted布林值，選用

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

overwrite布林值，選用

如果為 True，則以結果覆寫 csgraph。這僅在 method == ‘FW’ 且 csgraph 是具有 dtype=float64 的密集、c 順序陣列時適用。

indicesarray_like 或 int，選用

如果指定，則僅計算從給定索引的點開始的路徑。與 method == ‘FW’ 不相容。

傳回值:
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

如果圖中存在負環

注意事項

如同目前實作的方式，當 directed == False 時，Dijkstra 演算法和 Johnson 演算法不適用於具有方向相依距離的圖。亦即，如果 csgraph[i,j] 和 csgraph[j,i] 是不相等的邊，則 method=’D’ 可能會產生不正確的結果。

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

範例

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

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