scipy.sparse.csgraph.dijkstra¶
- scipy.sparse.csgraph.dijkstra(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False, limit=np.inf, min_only=False)¶
基于Fibonacci堆的Dijkstra算法
0.11.0 新版功能.
- 参数
- csgraph阵列、矩阵或稀疏矩阵，2维
表示输入图形的非负距离的N x N数组。
- directed布尔值，可选
如果为True(默认值)，则在有向图上查找最短路径：仅沿路径csgraph从i点移动到j点 [i, j] 并沿着路径csgraph从点j到i [j, i] 。如果为false，则在无向图上查找最短路径：算法可以沿着任一csgraph从i点前进到j或j前进到i。 [i, j] 或csgraph [j, i] 。
- indicesARRAY_LIKE或INT，可选
如果指定，则仅计算从给定索引处的点开始的路径。
- return_predecessors布尔值，可选
如果为True，则返回大小(N，N)前置或矩阵
- unweighted布尔值，可选
如果为True，则查找未加权的距离。也就是说，不是寻找每个点之间的路径以使权重之和最小化，而是寻找路径以使边的数量最小化。
- limit浮动，可选
要计算的最大距离必须>=0。使用较小的限制将通过中止由距离>限制分隔的对之间的计算来减少计算时间。对于此类对，距离将等于np.inf(即，未连接)。
0.14.0 新版功能.
- min_only布尔值，可选
如果为False(默认值)，则对于图形中的每个节点，查找从索引中的每个节点到每个节点的最短路径。如果为True，则对于图形中的每个节点，查找从索引中的任何节点到该节点的最短路径(这样可以大大加快速度)。
1.3.0 新版功能.
- 退货
- dist_matrixndarray，形状( [n_indices, ] N_节点，)
图形节点之间的距离矩阵。如果MIN_ONLY=FALSE，则DIST_MATRIX具有形状(n_索引，n_节点)和DIST_MATRIX [i, j] 给出沿图形从点i到点j的最短距离。如果MIN_ONLY=True，则dist_Matrix具有形状(n_node，)，并包含给定节点从索引中的任何节点到该节点的最短路径。
- predecessorsndarray，形状( [n_indices, ] N_节点，)
如果MIN_ONLY=FALSE，则它具有Shape(n_index，n_node)，否则它具有Shape(n_Nodes，)。仅当RETURN_PREPRECESSES==True时返回。前置任务的矩阵，可用于重建最短路径。前导矩阵的行i包含关于从点i开始的最短路径的信息：每个条目前导 [i, j] 给出从点i到点j的路径中上一个节点的索引。如果点i和j之间不存在路径，则前置节点 [i, j] =-9999
- sourcesndarray，形状(n_node，)
仅当MIN_ONLY=True且RETURN_PREPRECESSES=True时返回。包含到每个目标的路径最短的源的索引。如果限制内不存在路径，则将包含-9999。所传递的索引处的值将等于该索引(即到达节点i的最快方式是从节点i开始)。
注意事项
正如当前实现的那样，Dijkstra的算法在Directed==False时不适用于具有方向相关距离的图。即，如果csgraph [i,j] 和csgraph [j,i] 不相等并且两者都非零，则设置directed=false将不会产生正确的结果。
此外，此例程不适用于距离为负的图形。负距离可能导致无限循环，必须由专门的算法处理，如贝尔曼-福特算法或约翰逊算法。
示例
>>> 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) (0, 1) 1 (0, 2) 2 (1, 3) 1 (2, 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)