scipy.sparse.csgraph.

bellman_ford#

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

使用 Bellman-Ford 演算法計算最短路徑長度。

Bellman-Ford 演算法可以穩健地處理具有負權重的圖形。如果偵測到負環，則會引發錯誤。對於沒有負邊權重的圖形，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 bellman_ford

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