scipy.sparse.csgraph.bellman_ford¶
- scipy.sparse.csgraph.bellman_ford(csgraph, directed=True, indices=None, return_predecessors=False, unweighted=False)¶
使用Bellman-Ford算法计算最短路径长度。
Bellman-Ford算法可以很好地处理负权图。如果检测到负周期,则会引发错误。对于没有负边权的图,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 bellman_ford
>>> 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 = bellman_ford(csgraph=graph, directed=False, indices=0, return_predecessors=True) >>> dist_matrix array([0., 1., 2., 2.]) >>> predecessors array([-9999, 0, 0, 1], dtype=int32)