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 新版功能.
- 参数
- csgraph阵列、矩阵或稀疏矩阵，2维
表示输入图形的N x N距离数组。
- method字符串 [‘AUTO’|‘FW’|‘D’] ，可选
用于最短路径的算法。选项包括：
- ‘AUTO’--(默认值)从‘FW’、‘D’、‘BF’或‘J’中选择最佳选项
基于输入数据。
- ‘FW’--弗洛伊德-沃肖尔算法。计算成本是
大约
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”--约翰逊的算法。就像贝尔曼-福特算法一样，
约翰逊的算法是为权重为负值时使用而设计的。它将Bellman-Ford算法与Dijkstra算法相结合，提高了计算速度。
- directed布尔值，可选
如果为True(默认值)，则在有向图上查找最短路径：仅沿路径csgraph从i点移动到j点 [i, j] 。如果为false，则在无向图上查找最短路径：算法可以沿着csgraph从i点前进到j点。 [i, j] 或csgraph [j, i]
- return_predecessors布尔值，可选
如果为True，则返回大小(N，N)前置或矩阵
- unweighted布尔值，可选
如果为True，则查找未加权的距离。也就是说，不是寻找每个点之间的路径以使权重之和最小化，而是寻找路径以使边的数量最小化。
- overwrite布尔值，可选
如果为True，则用结果覆盖csgraph。仅当method==‘fw’并且csgraph是具有dtype=float64的密集c有序数组时，这才适用。
- indicesARRAY_LIKE或INT，可选
如果指定，则仅计算从给定索引处的点开始的路径。与方法==‘fw’不兼容。
- 退货
- dist_matrixndarray
图形节点之间的距离的N x N矩阵。DIST_矩阵 [i,j] 给出沿图形从点i到点j的最短距离。
- predecessorsndarray
仅当RETURN_PREPRECESSES==True时返回。前置任务的N x N矩阵，可用于重建最短路径。前导矩阵的行i包含关于从点i开始的最短路径的信息：每个条目前导 [i, j] 给出从点i到点j的路径中上一个节点的索引。如果点i和j之间不存在路径，则前置节点 [i, j] =-9999
- 加薪
- NegativeCycleError：
如果图中有负圈
注意事项
按照目前的实现，Dijkstra算法和Johnson算法在有向==False时不适用于具有方向相关距离的图。即，如果csgraph [i,j] 和csgraph [j,i] 是不相等的边，则方法=‘D’可能会产生不正确的结果。
示例
>>> from scipy.sparse import csr_matrix >>> 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_matrix(graph) >>> print(graph) (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)