johnson#
- scipy.sparse.csgraph.johnson(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False)#
使用 Johnson 算法计算最短路径长度。
Johnson 算法结合了 Bellman-Ford 算法和 Dijkstra 算法,可以快速找到最短路径,并且对负环的存在具有鲁棒性。 如果检测到负环,则会引发错误。 对于没有负边权重的图,dijkstra 可能会更快。
在 0.11.0 版本中添加。
- 参数:
- csgraph类数组对象,或稀疏数组或矩阵,2 维
表示输入图的 N x N 距离数组。
- directedbool,可选
如果为 True(默认),则在有向图上找到最短路径:仅沿路径 csgraph[i, j] 从点 i 移动到点 j。 如果为 False,则在无向图上找到最短路径:该算法可以沿 csgraph[i, j] 或 csgraph[j, i] 从点 i 进行到 j
- indices类数组对象或 int,可选
如果指定,则仅计算从给定索引处的点开始的路径。
- return_predecessorsbool,可选
如果为 True,则返回大小为 (N, N) 的前驱矩阵。
- unweightedbool,可选
如果为 True,则找到未加权距离。 也就是说,不是找到每个点之间的路径使得权重之和最小化,而是找到边数最小化的路径。
- 返回值:
- dist_matrixndarray
图节点之间的 N x N 距离矩阵。 dist_matrix[i,j] 给出了沿图从点 i 到点 j 的最短距离。
- predecessorsndarray,形状 (n_indices, n_nodes,)
仅当 return_predecessors == True 时返回。 如果 indices 为 None,则
n_indices = n_nodes
并且矩阵的形状变为(n_nodes, n_nodes)
。 前驱矩阵,可用于重建最短路径。 前驱矩阵的第 i 行包含有关从点 i 出发的最短路径的信息:每个条目 predecessors[i, j] 给出从点 i 到点 j 的路径中的前一个节点的索引。 如果点 i 和 j 之间不存在路径,则 predecessors[i, j] = -9999
- 引发:
- NegativeCycleError
如果图中存在负环
注释
此例程专门为具有负边权重的图设计。 如果所有边权重均为正,则 Dijkstra 算法是更好的选择。
如果存在多个有效的解决方案,则输出可能会因 SciPy 和 Python 版本而异。
示例
>>> from scipy.sparse import csr_array >>> 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_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 = 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)