SciPy 图结构

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))

Floyd Warshall -- 弗洛伊德算法

弗洛伊德算法算法是解决任意两点间的最短路径的一种算法。

Scipy 使用 floyd_warshall() 方法来查找所有元素对之间的最短路径。

查找所有元素对之间的最短路径径：

import numpy as np
from scipy. sparse . csgraph import floyd_warshall
from scipy. sparse import csr_matrix
arr = np. array ( [
[ 0 , 1 , 2 ] ,
[ 1 , 0 , 0 ] ,
[ 2 , 0 , 0 ]
newarr = csr_matrix ( arr )
print ( floyd_warshall ( newarr , return_predecessors = True ) )

以上代码输出结果为：

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

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))

深度优先顺序

depth_first_order() 方法从一个节点返回深度优先遍历的顺序。

可以接收以下参数：

图开始遍历的元素

给定一个邻接矩阵，返回深度优先遍历的顺序：

import numpy as np
from scipy. sparse . csgraph import depth_first_order
from scipy. sparse import csr_matrix
arr = np. array ( [
[ 0 , 1 , 0 , 1 ] ,
[ 1 , 1 , 1 , 1 ] ,
[ 2 , 1 , 1 , 0 ] ,
[ 0 , 1 , 0 , 1 ]
newarr = csr_matrix ( arr )
print ( depth_first_order ( newarr , 1 ) )

以上代码输出结果为：

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

广度优先顺序

breadth_first_order() 方法从一个节点返回广度优先遍历的顺序。

可以接收以下参数：

图开始遍历的元素

给定一个邻接矩阵，返回广度优先遍历的顺序：

import numpy as np
from scipy. sparse . csgraph import breadth_first_order
from scipy. sparse import csr_matrix
arr = np. array ( [
[ 0 , 1 , 0 , 1 ] ,
[ 1 , 1 , 1 , 1 ] ,
[ 2 , 1 , 1 , 0 ] ,
[ 0 , 1 , 0 , 1 ]
newarr = csr_matrix ( arr )
print ( breadth_first_order ( newarr , 1 ) )

以上代码输出结果为：

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