3.8.2 最短路径
稀疏矩阵w可以用于表示图，w[i, j]保存图中节点i和节点j之间路径的权值。若节点i与j之间没有直接路径，则稀疏矩阵不包含该下标，因此使用稀疏矩阵可以表示权值为0的路径。
我们对图3-48中A、B、C、D这4个节点分别编号为0、1、2、3，于是可以构造如下稀疏矩阵。注意当将稀疏矩阵转换为数组显示时，矩阵中未设置的值默认为0，这并不表示图中有权值为0的边。当用稀疏矩阵表示无向图时，只需要设置w[i, j]或w[j, i]中的一个即可。
图3-48 使用稀疏矩阵可以表示有向图
w = sparse.dok_matrix((4, 4))
edges = [(0, 1, 10), (1, 2, 5), (0, 2, 3),
(2, 3, 7), (3, 0, 4), (3, 2, 6)]
for i, j, v in edges:
w[i, j] = v
w.todense( )
matrix([[ 0., 10., 3., 0.],
[ 0., 0., 5., 0.],
[ 0., 0., 0., 7.],
[ 4., 0., 6., 0.]])
使用scipy.sparse.scgraph模块可以在图中寻找最短路径，下面通过一个例子说明最短路径函数的用法。
图3-49（左）是一幅迷宫图像，其中的黑色曲线是用scgraph模块求得的从坐标(sx, sy)到(ex, ey)的最短路径。❶为了方便计算，下面先将彩色迷宫图像通过阈值转换为黑白二值图像，黑色表示墙壁，白色表示通路。❷为了避免将迷宫外部的余白当作通路，下面的程序在中部两侧添加了两条黑色线段，将余白分隔为上下两个部分。经过上述处理之后的迷宫如图3-49（右）所示。
图3-49 用dijkstra计算最短路径
img = pl.imread("maze.png")
sx, sy = (400, 979)
ex, ey = (398, 25)
bimg = np.all(img > 0.81, axis=2) ❶
H, W = bimg.shape
x0, x1 = np.where(bimg[H//2, :]==0)[0][[0, -1]] ❷
bimg[H//2, :x0] = 0
bimg[H//2, x1:] = 0
我们将迷宫中所有的像素都当作图中的节点，节点序号与像素坐标(x, y)的关系使用idx=y* W + x计算。❶找到所有上下相邻、左右相邻的白色像素对，将其对应的节点序号保存在形状为(N, 2)的edges数组中，N为图所包含的边数。❷通过coo_matrix( )创建稀疏矩阵，所有边的权值均为1。
#上下相邻的白色像素
mask = (bimg[1:, :] & bimg[:-1, :])
idx = np.where(mask.ravel( ))[0]
vedge = np.c_[idx, idx + W]
pl.imsave("tmp.png", mask, cmap="gray")
#左右相邻的白色像素
mask = (bimg[:, 1:] & bimg[:, :-1])
y, x = np.where(mask)
idx = y *
W + x
hedge = np.c_[idx, idx + 1]
edges = np.vstack([vedge, hedge]) ❶
values = np.ones(edges.shape[0])
w = sparse.coo_matrix((values, (edges[:, 0], edges[:, 1])), ❷
shape=(bimg.size, bimg.size))
接下来导入csgraph模块，并调用dijkstra( )计算从编号为startid的节点出发到达所有其他节点的最短路径。directed参数为False表示无向图，为了计算最短路径，需要设置return_predecessors参数为True。所返回的数组d和p的形状为（indices参数的长度，图的总节点数）。
from scipy.sparse import csgraph
startid = sy *
W + sx
endid = ey *
W + ex
d, p = csgraph.dijkstra(w, indices=[startid], return_predecessors=True, directed=False)
d.shape p.shape
----------- -----------
(1, 801600) (1, 801600)
d[i, j]保存从编号为indices[i]的节点到编号为j的节点的距离。如果两个节点之间无路径联通，值为inf。下面计算从起点无法到达的节点数，这些节点包括迷宫中黑色像素表示的墙壁以及被黑色像素完全包围的区域。
np.isinf(d[0]).sum( )
322324
p[i, j]保存节点indices[i]到节点j的路径中最后一个节点的编号。下面的代码从编号为endid的节点开始回溯，直到找到startid节点为止。将访问过的节点保存到path中，将path反转即可得到从起点到终点的路径。
path = [ ]
node_id = endid
while True:
path.append(node_id)
if node_id == startid or node_id < 0:
break
node_id = p[0, node_id]
path = np.array(path)
最后，在原来的迷宫图像中将path经过的像素涂黑，得到图3-49（左）中的路径。
scpy2.scipy.hrd_solver使用csgraph计算华容道游戏“横刀立马”布局步数最少的解法。
在上面的迷宫中，两个相邻白色像素之间的路径权值均为1，因此搜索到的最佳路径为最短路径。而许多游戏地图中的路径搜索会考虑地形因素，这时可以根据不同的地形设置不同大小的路径权值，这样最佳路径就是使所有权值之和最小的路径。