sklearn.utils.sklearn.utils.graph_shortest_path.graph_shortest_path?
sklearn.utils.graph_shortest_path.graph_shortest_path()
對正有向圖或無向圖執行最短路徑圖搜索。
| 參數 | 說明 |
|---|---|
| dist_matrix | arraylike or sparse matrix, shape = (N,N) 正距離數組。 如果頂點i連接到頂點j，則dist_matrix [i,j]給出頂點之間的距離。 如果頂點i未連接到頂點j，則dist_matrix [i,j] = 0 |
| directed | boolean 如果為真，則在有向圖上找到最短路徑：僅從一個點到其相鄰點，而不是反過來。 如果為假，則在無向圖上找到最短路徑：該算法可以從一個點前進到其相鄰點，反之亦然。 |
| method | string [‘auto’，’FW’，’D’] 使用方法。 選項為“auto”：嘗試為當前問題選擇最佳方法。“FW”：Floyd-Warshall算法。 O [N ^ 3]“ D”：Dijkstra的斐波那契堆棧算法。 O [（k + log（N））N ^ 2] |
| 返回值 | 說明 |
|---|---|
| G | np.ndarray, float, shape = [N,N] G [i，j]給出沿曲線圖從點i到點j的最短距離。 |
注:
按照目前的實現方式，當有向== False時，Dijkstra的算法不適用于方向與距離相關的圖形。 也就是說，如果dist_matrix [i,j]和dist_matrix [j,i]不相等且都不為零，則method ='D'不一定會得出正確的結果。
同樣，這些例程尚未針對負距離的圖形進行過測試。 負距離會導致無限循環，必須由專門的算法處理。