dijkstra#
- scipy.sparse.csgraph.dijkstra(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False, limit=np.inf, min_only=False)#
使用斐波那契堆的迪杰斯特拉算法
在版本 0.11.0 中添加。
- 参数：
- csgraph数组、矩阵或稀疏矩阵，二维
表示输入图的 N x N 非负距离数组。
- directed布尔值，可选
如果为 True（默认值），则在有向图上找到最短路径：仅沿着路径 csgraph[i, j] 从点 i 移动到点 j，沿着路径 csgraph[j, i] 从点 j 移动到点 i。如果为 False，则在无向图上找到最短路径：算法可以沿着 csgraph[i, j] 或 csgraph[j, i] 从点 i 移动到点 j 或从点 j 移动到点 i。
警告
在使用
directed=False时，请参考下面的说明。- indices类似数组或整数，可选
如果指定，则只计算从给定索引处的点开始的路径。
- return_predecessors布尔值，可选
如果为 True，则返回大小为 (N, N) 的前驱矩阵。
- unweighted布尔值，可选
如果为 True，则查找无权重距离。也就是说，与其找到使权重总和最小化的每点之间的路径，不如找到使边数最小化的路径。
- limit浮点数，可选
要计算的最大距离，必须 >= 0。使用较小的 limit 将通过中止距离 > limit 的对之间的计算来减少计算时间。对于此类对，距离将等于 np.inf（即，未连接）。
在版本 0.14.0 中添加。
- min_only布尔值，可选
如果为 False（默认值），则对于图中的每个节点，找到从索引中的每个节点到该节点的最短路径。如果为 True，则对于图中的每个节点，找到从索引中的任何节点到该节点的最短路径（这可能快得多）。
在版本 1.3.0 中添加。
- 返回值：
- dist_matrixndarray，形状 ([n_indices, ]n_nodes,)
图节点之间距离的矩阵。如果 min_only=False，则 dist_matrix 的形状为 (n_indices, n_nodes)，dist_matrix[i, j] 给出沿图从点 i 到点 j 的最短距离。如果 min_only=True，则 dist_matrix 的形状为 (n_nodes,)，对于给定节点，它包含从索引中的任何节点到该节点的最短路径。
- predecessorsndarray，形状 ([n_indices, ]n_nodes,)
如果 min_only=False，则形状为 (n_indices, n_nodes)，否则形状为 (n_nodes,)。仅在 return_predecessors == True 时返回。前驱矩阵，可用于重建最短路径。前驱矩阵的第 i 行包含关于从点 i 开始的最短路径的信息：每个条目 predecessors[i, j] 给出从点 i 到点 j 的路径中前一个节点的索引。如果点 i 和 j 之间不存在路径，则 predecessors[i, j] = -9999
- sourcesndarray，形状 (n_nodes,)
仅在 min_only=True 且 return_predecessors=True 时返回。包含对每个目标具有最短路径的源的索引。如果在限制范围内不存在路径，则将包含 -9999。传递的索引处的值将等于该索引（即，到达节点 i 的最快方式是从节点 i 开始）。
说明
如当前实现，当 directed == False 时，迪杰斯特拉算法不适用于具有方向依赖距离的图。即，如果 csgraph[i,j] 和 csgraph[j,i] 不相等且都非零，则设置 directed=False 将不会产生正确的结果。
此外，此例程不适用于具有负距离的图。负距离会导致无限循环，必须由专用算法（例如贝尔曼-福特算法或约翰逊算法）处理。
如果可能存在多个有效解，输出可能会随 SciPy 和 Python 版本而异。
示例
>>> from scipy.sparse import csr_matrix >>> from scipy.sparse.csgraph import dijkstra
>>> graph = [ ... [0, 1, 2, 0], ... [0, 0, 0, 1], ... [0, 0, 0, 3], ... [0, 0, 0, 0] ... ] >>> graph = csr_matrix(graph) >>> print(graph) (np.int32(0), np.int32(1)) 1 (np.int32(0), np.int32(2)) 2 (np.int32(1), np.int32(3)) 1 (np.int32(2), np.int32(3)) 3
>>> dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, indices=0, return_predecessors=True) >>> dist_matrix array([0., 1., 2., 2.]) >>> predecessors array([-9999, 0, 0, 1], dtype=int32)