SciPy 教程 之 SciPy 图结构 3

SciPy 教程 之 SciPy 图结构 3

SciPy 图结构

图结构是算法学中最强大的框架之一。

图是各种关系的节点和边的集合，节点是与对象对应的顶点，边是对象之间的连接。

SciPy 提供了 scipy.sparse.csgraph 模块来处理图结构。

Dijkstra -- 最短路径算法

Dijkstra(迪杰斯特拉)最短路径算法，用于计算一个节点到其他所有节点的最短路径。

Scipy 使用 dijkstra() 方法来计算一个元素到其他元素的最短路径。

dijkstra() 方法可以设置以下几个参数：
return_predecessors: 布尔值，设置 True，遍历所有路径，如果不想遍历所有路径可以设置为 False。
indices: 元素的索引，返回该元素的所有路径。
limit: 路径的最大权重。

实例

查找元素 1 到 2 的最短路径：

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
[0, 1, 2],
[1, 0, 0],
[2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))

以上代码输出结果为：

(array([ 0., 1., 2.]), array([-9999, 0, 0], dtype=int32))