Ctrl+K
scipy.sparse.csgraph.

dijkstra#

scipy.sparse.csgraph.dijkstra(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False, limit=np.inf, min_only=False)#

使用費波那契堆的戴克斯特拉演算法

在 0.11.0 版本中新增。

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

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

directedbool，選用

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

警告

使用 directed=False 時，請參考以下注意事項。

indicesarray_like 或 int，選用

如果指定，則僅計算從給定索引點開始的路徑。

return_predecessorsbool，選用

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

unweightedbool，選用

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

limitfloat，選用

要計算的最大距離，必須 >= 0。使用較小的限制將通過中止距離 > limit 的配對之間的計算來減少計算時間。對於此類配對，距離將等於 np.inf（即，未連接）。

在 0.14.0 版本中新增。

min_onlybool，選用

如果為 False（預設），對於圖形中的每個節點，找到從索引中每個節點到該節點的最短路徑。如果為 True，對於圖形中的每個節點，找到從索引中任何節點到該節點的最短路徑（這可能會快得多）。

在 1.3.0 版本中新增。

返回:
dist_matrixndarray，形狀 ([n_indices, ]n_nodes,)

圖形節點之間距離的矩陣。如果 min_only=False，則 dist_matrix 的形狀為 (n_indices, n_nodes)，dist_matrix[i, j] 給出從點 i 到點 j 沿圖形的最短距離。如果 min_only=True，則 dist_matrix 的形狀為 (n_nodes,)，並包含給定節點從索引中任何節點到該節點的最短路徑。

predecessorsndarray，形狀 ([n_indices, ]n_nodes,)

如果 min_only=False，則此形狀為 (n_indices, n_nodes)，否則形狀為 (n_nodes,)。僅當 return_predecessors == True 時返回。前導矩陣，可用於重建最短路徑。前導矩陣的第 i 行包含從點 i 出發的最短路徑資訊：每個條目 predecessors[i, j] 給出從點 i 到點 j 的路徑中前一個節點的索引。如果點 i 和 j 之間不存在路徑，則 predecessors[i, j] = -9999

sourcesndarray，形狀 (n_nodes,)

僅當 min_only=True 且 return_predecessors=True 時返回。包含具有到每個目標最短路徑的來源索引。如果在限制內不存在路徑，則這將包含 -9999。傳遞的索引處的值將等於該索引（即，到達節點 i 的最快方法是從節點 i 開始）。

注意

如同目前實作的，當 directed == False 時，戴克斯特拉演算法不適用於具有方向相關距離的圖形。也就是說，如果 csgraph[i,j] 和 csgraph[j,i] 不相等且兩者均為非零值，則設定 directed=False 將不會產生正確的結果。

此外，此例程不適用於具有負距離的圖形。負距離可能導致無限循環，必須由專門的演算法（例如貝爾曼-福特演算法或約翰遜演算法）處理。

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

範例

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

>>> graph = [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [0, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)
<Compressed Sparse Row sparse array of dtype 'int64'
    with 4 stored elements and shape (4, 4)>
    Coords  Values
    (0, 1)  1
    (0, 2)  2
    (1, 3)  1
    (2, 3)  3

>>> dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, indices=0, return_predecessors=True)
>>> dist_matrix
array([0., 1., 2., 2.])
>>> predecessors
array([-9999,     0,     0,     1], dtype=int32)
本頁面