SciPy 教程 之 SciPy 图结构 5
SciPy 图结构
图结构是算法学中最强大的框架之一。
图是各种关系的节点和边的集合,节点是与对象对应的顶点,边是对象之间的连接。
SciPy 提供了 scipy.sparse.csgraph 模块来处理图结构。
Bellman Ford -- 贝尔曼-福特算法
贝尔曼-福特算法是解决任意两点间的最短路径的一种算法。
Scipy 使用 bellman_ford() 方法来查找所有元素对之间的最短路径,通常可以在任何图中使用,包括有向图、带负权边的图。
实例
使用负权边的图查找从元素 1 到元素 2 的最短路径:
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
arr = np.array([
[0, -1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(bellman_ford(newarr, return_predecessors=True, indices=0))
以上代码输出结果为:
(array([ 0., -1., 2.]), array([-9999, 0, 0], dtype=int32))