scipy.sparse.csgraph.
floyd_warshall#
- scipy.sparse.csgraph.floyd_warshall(csgraph, directed=True, return_predecessors=False, unweighted=False, overwrite=False)#
使用 Floyd-Warshall 算法计算最短路径长度
在 0.11.0 版本中添加。
- 参数:
- csgraph类数组,或稀疏数组或矩阵,2 维
表示输入图的 N x N 距离数组。
- directedbool,可选
如果为 True(默认),则在有向图上找到最短路径:仅沿路径 csgraph[i, j] 从点 i 移动到点 j。 如果为 False,则在无向图上找到最短路径:算法可以沿 csgraph[i, j] 或 csgraph[j, i] 从点 i 行进到点 j
- return_predecessorsbool,可选
如果为 True,则返回大小为 (N, N) 的前驱矩阵。
- unweightedbool,可选
如果为 True,则查找未加权距离。 也就是说,与其找到每点之间的路径使得权重之和最小化,不如找到使边数最小化的路径。
- overwritebool,可选
如果为 True,则使用结果覆盖 csgraph。 这仅适用于 csgraph 是一个密集的、c 顺序的、dtype=float64 的数组。
- 返回值:
- 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
如果图中存在负循环
备注
如果存在多个有效解决方案,则输出可能随 SciPy 和 Python 版本而变化。
示例
>>> from scipy.sparse import csr_array >>> from scipy.sparse.csgraph import floyd_warshall
>>> 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 = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True) >>> dist_matrix array([[0., 1., 2., 2.], [1., 0., 3., 1.], [2., 3., 0., 3.], [2., 1., 3., 0.]]) >>> predecessors array([[-9999, 0, 0, 1], [ 1, -9999, 0, 1], [ 2, 0, -9999, 2], [ 1, 3, 3, -9999]], dtype=int32)