1
应用实践
1．程序设计：给定图 G = < V, E >，试计算 G 中结点 v
i
到 v
j
长度为 m 的通路数。
（1）设计思路
输入：图 G = < V, E >，v
i
和 v
j
。
输出：v
i
到 v
j
长度为 m 的通路数。
实现语言：C 语言。
基本思路：由定理 6.3，计算 A 的 m 次幂 A
m
＝(
( )m
ij
a
)
nxn
，其中的
( )m
ij
a
即为从结点 v
i
到
结点 v
j
长度为 m 的通路数目。
（2）伪代码
/* 输入：图 G 的邻接矩阵 A，m，i，j */
begin
Matrix result = A
for (var count = 1; count < m; count++) do
result = result * A;
return result[i][j];
end
（3）参考源代码（链接）
2．程序设计：给定赋权图 G = < V, E, g >，计算 v
i
到 v
j
的最短通路长度。
（1）设计思路
输入：赋权图 G = < V, E, g >，v
i
和 v
j
。
输出：v
i
到 v
j
的最短通路长度。
实现语言：C 语言。
基本思路：使用算法 6.2（Floyd 算法）计算。
从矩阵 D
(0)
＝(w
ij
)
n×n
（这里 w
ij
＝w(v
i
,v
j
)，称为图的长度矩阵）开始，依次构造出 n 个矩
阵 D
(1)
, D
(2)
, …, D
(n)
，这里 n 为图中结点的个数。第 k 个矩阵 D
(k)
＝(
( )k
ij
d
)
n×n
的元素
( )k
ij
d
表示从
结点 v
i
到 v
j
而中间结点仅属于 v
1
到 v
k
的 k 个结点的所有通路中的最短通路长度。
若已知 D
(k-1)
＝(
( 1)k
ij
d
-
)
n×n
，则 D
(k)
＝(
( )k
ij
d
)
n×n
的元素规定为
( ) ( 1) ( 1) ( 1)
min{ , }
k k k k
ij ij ik kj
d d d d
- - -
= +
（2）伪代码
/* 输入赋权图 G 的带权邻接矩阵 A ，矩阵 P 记录最短路径*/
begin
for(i = 1; i < n; i++) do
