scipy.sparse.csgraph.johnson¶
- scipy.sparse.csgraph.johnson(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False)¶
使用Johnson算法计算最短路径长度。
约翰逊的算法结合了贝尔曼-福特算法和迪克斯特拉的算法，以一种对负循环的存在具有鲁棒性的方式快速找到最短路径。如果检测到负周期，则会引发错误。对于没有负边权的图，Dijkstra可能更快。
0.11.0 新版功能.
- 参数
- csgraph阵列、矩阵或稀疏矩阵，2维
表示输入图形的N x N距离数组。
- directed布尔值，可选
如果为True(默认值)，则在有向图上查找最短路径：仅沿路径csgraph从i点移动到j点 [i, j] 。如果为false，则在无向图上查找最短路径：算法可以沿着csgraph从i点前进到j点。 [i, j] 或csgraph [j, i]
- indicesARRAY_LIKE或INT，可选
如果指定，则仅计算从给定索引处的点开始的路径。
- return_predecessors布尔值，可选
如果为True，则返回大小(N，N)前置或矩阵
- unweighted布尔值，可选
如果为True，则查找未加权的距离。也就是说，不是寻找每个点之间的路径以使权重之和最小化，而是寻找路径以使边的数量最小化。
- 退货
- 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算法是更好的选择。
示例
>>> from scipy.sparse import csr_matrix >>> from scipy.sparse.csgraph import johnson
>>> 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 = johnson(csgraph=graph, directed=False, indices=0, return_predecessors=True) >>> dist_matrix array([0., 1., 2., 2.]) >>> predecessors array([-9999, 0, 0, 1], dtype=int32)