scipy.sparse.csgraph.floyd_warshall¶
- scipy.sparse.csgraph.floyd_warshall(csgraph, directed=True, return_predecessors=False, unweighted=False, overwrite=False)¶
使用弗洛伊德-沃肖尔算法计算最短路径长度
0.11.0 新版功能.
- 参数
- csgraph阵列、矩阵或稀疏矩阵，2维
表示输入图形的N x N距离数组。
- 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。只有当csgraph是密集的c有序数组且dtype=float64时，这才适用。
- 退货
- 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：
如果图中有负圈
示例
>>> from scipy.sparse import csr_matrix >>> 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_matrix(graph) >>> print(graph) (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)