根据“邻接矩阵”计算图（有向无向混合负权均可）中“从任意一个顶点到任意一个顶点的最短路长”
算法,邻接矩阵C
记C1=C
对k=2 3 4 5 6等，令Ck=Ck-1乘以C
定义：第i行与第j列之元素对应向加之最小值直到有 Ck=Ck-1 为止。
例：此题取自“《运筹学》孔造杰编机械工业出版”第208页第6题。已知邻接矩阵C
，，
注解：元素5表示从到的边权。
，，
略手工计算，以下用机器算。
程序清单：
clear
c=inf*ones(6,6);
for i=1:6
c(i,i)=0;
end
c(1,2)=1;c(1,4)=2;c(2,3)=3;c(2,4)=-1;c(3,4)=5;c(3,6)=2;c(4,5)=-3;c(5,3)=2;c(5,6)=2;
d=c,
for xh=1:10
for i=1:6
for j=1:6
a(i,j)=min(d(i,:)+c(:,j)');
end
end
xhcs=xh+1,d=a
end
执行结果：
C2为
0 1 4 0 -1 Inf
Inf 0 3 -1 -4 5
Inf Inf 0 5 2 2
Inf Inf -1 0 -3 -1
Inf Inf 2 7 0 2
Inf Inf Inf Inf Inf 0
C3为
0 1 1 0 -3 1
Inf 0 -2 -1 -4 -2
Inf Inf 0 5 2 2
Inf Inf -1 0 -3 -1
Inf Inf 2 7 0 2
Inf Inf Inf Inf Inf 0
C4为
0 1 -1 0 -3 -1
Inf 0 -2 -1 -4 -2
Inf Inf 0 5 2 2
Inf Inf -1 0 -3 -1
Inf Inf 2 7 0 2
Inf Inf Inf Inf Inf 0
此时，C3与C4相同，故它就是最后结果。
例：此题取自“《数学实验》刘琼荪编高等教育出版”第193页之图13.3 。已知邻接矩阵C
程序清单：
clear
c=inf*ones(27,27);
for i=1:27
c(i,i)=0;
end
c(1,2)=8.9;c(1,9)=9.8;c(2,3)=9.3;c(2,10)=10;c(3,4)=4.5;c(3,27)=9.6;c(4,5)=3.5;c(4,27)=6.2;c(5,6)=7.7;c(5,12)=9.9;c(6,7)=4.9;c(6,13)=9.5;c(7,8)=6.1;c(7,14)=9.6;c(8,15)=10;c(9,10)=9.8;c(9,17)=13.8;c(10,11)=12.5;c(10,18)=14.2;c(11,12)=3.6;c(11,16)=3.3;c(11,27)=3.7;c(12,13)=7.4;c(12,16)=3.1;c(13,14)=5.0;c(14,15)=7.3;c(15,21)=10.7;c(16,20)=10.4;c(17,18)=10.8;c(18,19)=5;c(18,22)=4.8;c(19,20)=9.4;c(19,23)=4.7;c(20,21)=21.2;c(20,24)=6.6;c(21,26)=8;c(22,23)=5;c(23,24)=9.2;c(24,25)=15.1;c(25,26)=7.1;
d=c,
for xh=1:20
for i=1:27
for j=1:27
a(i,j)=min(d(i,:)+c(:,j)');
end
end
hhh=0;
for ii=1:27
for jj=1:27
hhh=hhh+abs(a(ii,jj)-d(ii,jj));
end
end
if hhh==0
break
end
xhcs=xh+1,d=a
end
执行结果：(迭代计算了9次就发现结果不变了，下面矩阵d的第i行第j列元素即为第i号点到第j号点的最短长度)。
xhcs = 9
d =
Columns 1 through 15
0 8.9000 18.2000 22.7000 26.2000 33.9000 38.8000 44.9000 9.8000 18.9000 31.4000 35.0000 42.4000 47.4000 54.7000
8.9000 0 9.3000 13.8000 17.3000 25.0000 29.9000 36.0000 18.7000 10.0000 22.5000 26.1000 33.5000 38.5000 45.8000
18.2000 9.3000 0 4.5000 8.0000 15.7000 20.6000 26.7000 28.0000 19.3000 13.3000 16.9000 24.3000 29.3000 36.6000
22.7000 13.8000 4.5000 0 3.5000 11.2000 16.1000 22.2000 32.2000 22.4000 9.9000 13.4000 20.7000 25.7000 32.2000
26.2000 17.3000 8.0000 3.5000 0 7.7000 12.6000 18.7000 35.7000 25.9000 13.4000 9.9000 17.2000 22.2000 28.7000
33.9000 25.0000 15.7000 11.2000 7.7000 0 4.9000 11.0000 42.8000 33.0000 20.5000 16.9000 9.5000 14.5000 21.0000
38.8000 29.9000 20.6000 16.1000 12.6000 4.9000 0 6.1000 47.7000 37.9000 25.4000 21.8000 14.4000 9.6000 16.1000
44.9000 36.0000 26.7000 22.2000 18.7000 11.0000 6.1000 0 53.8000 44.0000 31.5000 27.9000 20.5000 15.7000 10.0000
9.8000 18.7000 28.0000 32.2000 35.7000 42.8000 47.7000 53.8000 0 9.8000 22.3000 25.9000 33.3000 38.3000 45.6000
18.9000 10.0000 19.3000 22.4000 25.9000 33.0000 37.9000 44.0000 9.8000 0 12.5000 16.1000 23.5000 28.5000 35.8000
31.4000 22.5000 13.3000 9.9000 13.4000 20.5000 25.4000 31.5000 22.3000 12.5000 0 3.6000 11.0000 16.0000 23.3000
35.0000 26.1000 16.9000 13.4000 9.9000 16.9000 21.8000 27.9000 25.9000 16.1000 3.6000 0 7.4000 12.4000 19.7000
42.4000 33.5000 24.3000 20.7000 17.2000 9.5000 14.4000 20.5000 33.3000 23.5000 11.0000 7.4000 0 5.0000 12.3000
47.4000 38.5000 29.3000 25.7000 22.2000 14.5000 9.6000 15.7000 38.3000 28.5000 16.0000 12.4000 5.0000 0 7.3000
54.7000 45.8000 36.6000 32.2000 28.7000 21.0000 16.1000 10.0000 45.6000 35.8000 23.3000 19.7000 12.3000 7.3000 0
34.7000 25.8000 16.6000 13.2000 13.0000 20.0000 24.9000 31.0000 25.6000 15.8000 3.3000 3.1000 10.5000 15.5000 22.8000
23.6000 32.5000 41.8000 46.0000 48.6000 55.6000 60.5000 66.6000 13.8000 23.6000 36.1000 38.7000 46.1000 51.1000 57.1000
33.1000 24.2000 33.5000 36.6000 37.8000 44.8000 49.7000 55.8000 24.0000 14.2000 26.7000 27.9000 35.3000 40.3000 46.3000
38.1000 29.2000 36.4000 33.0000 32.8000 39.8000 44.7000 50.8000 29.0000 19.2000 23.1000 22.9000 30.3000 35.3000 41.3000
45.1000 36.2000 27.0000 23.6000 23.4000 30.4000 35.3000 41.4000 36.0000 26.2000 13.7000 13.5000 20.9000 25.9000 31.9000
65.4000 56.5000 47.3000 42.9000 39.4000 31.7000 26.8000 20.7000 56.3000 46.5000 34.0000 30.4000 23.0000 18.0000 10.7000
37.9000 29.0000 38.3000 41.4000 42.5000 49.5000 54.4000 60.5000 28.8000 19.0000 31.5000 32.6000 40.0000 45.0000 51.0000
42.8000 33.9000 41.1000 37.7000 37.5000 44.5000 49.4000 55.5000 33.7000 23.9000 27.8000 27.6000 35.0000 40.0000 46.0000
51.7000 42.8000 33.6000 30.2000 30.0000 37.0000 41.9000 48.0000 42.6000 32.8000 20.3000 20.1000 27.5000 32.5000 38.5000
66.8000 57.9000 48.7000 45.3000 45.1000 46.8000 41.9000 35.8000 57.7000 47.9000 35.4000 35.2000 38.1000 33.1000 25.8000
73.4000 64.5000 55.3000 50.9000 47.4000 39.7000 34.8000 28.7000 64.3000 54.5000 42.0000 38.4000 31.0000 26.0000 18.7000
27.8000 18.9000 9.6000 6.2000 9.7000 17.4000 22.3000 28.4000 26.0000 16.2000 3.7000 7.3000 14.7000 19.7000 27.0000
Columns 16 through 27
34.7000 23.6000 33.1000 38.1000 45.1000 65.4000 37.9000 42.8000 51.7000 66.8000 73.4000 27.8000
25.8000 32.5000 24.2000 29.2000 36.2000 56.5000 29.0000 33.9000 42.8000 57.9000 64.5000 18.9000
16.6000 41.8000 33.5000 36.4000 27.0000 47.3000 38.3000 41.1000 33.6000 48.7000 55.3000 9.6000
13.2000 46.0000 36.6000 33.0000 23.6000 42.9000 41.4000 37.7000 30.2000 45.3000 50.9000 6.2000
13.0000 48.6000 37.8000 32.8000 23.4000 39.4000 42.5000 37.5000 30.0000 45.1000 47.4000 9.7000
20.0000 55.6000 44.8000 39.8000 30.4000 31.7000 49.5000 44.5000 37.0000 46.8000 39.7000 17.4000
24.9000 60.5000 49.7000 44.7000 35.3000 26.8000 54.4000 49.4000 41.9000 41.9000 34.8000 22.3000
31.0000 66.6000 55.8000 50.8000 41.4000 20.7000 60.5000 55.5000 48.0000 35.8000 28.7000 28.4000
25.6000 13.8000 24.0000 29.0000 36.0000 56.3000 28.8000 33.7000 42.6000 57.7000 64.3000 26.0000
15.8000 23.6000 14.2000 19.2000 26.2000 46.5000 19.0000 23.9000 32.8000 47.9000 54.5000 16.2000
3.3000 36.1000 26.7000 23.1000 13.7000 34.0000 31.5000 27.8000 20.3000 35.4000 42.0000 3.7000
3.1000 38.7000 27.9000 22.9000 13.5000 30.4000 32.6000 27.6000 20.1000 35.2000 38.4000 7.3000
10.5000 46.1000 35.3000 30.3000 20.9000 23.0000 40.0000 35.0000 27.5000 38.1000 31.0000 14.7000
15.5000 51.1000 40.3000 35.3000 25.9000 18.0000 45.0000 40.0000 32.5000 33.1000 26.0000 19.7000
22.8000 57.1000 46.3000 41.3000 31.9000 10.7000 51.0000 46.0000 38.5000 25.8000 18.7000 27.0000
0 35.6000 24.8000 19.8000 10.4000 31.6000 29.5000 24.5000 17.0000 32.1000 39.2000 7.0000
35.6000 0 10.8000 15.8000 25.2000 46.4000 15.6000 20.5000 29.7000 44.8000 51.9000 39.8000
24.8000 10.8000 0 5.0000 14.4000 35.6000 4.8000 9.7000 18.9000 34.0000 41.1000 30.4000
19.8000 15.8000 5.0000 0 9.4000 30.6000 9.7000 4.7000 13.9000 29.0000 36.1000 26.8000
10.4000 25.2000 14.4000 9.4000 0 21.2000 19.1000 14.1000 6.6000 21.7000 28.8000 17.4000
31.6000 46.4000 35.6000 30.6000 21.2000 0 40.3000 35.3000 27.8000 15.1000 8.0000 37.7000
29.5000 15.6000 4.8000 9.7000 19.1000 40.3000 0 5.0000 14.2000 29.3000 36.4000 35.2000
24.5000 20.5000 9.7000 4.7000 14.1000 35.3000 5.0000 0 9.2000 24.3000 31.4000 31.5000
17.0000 29.7000 18.9000 13.9000 6.6000 27.8000 14.2000 9.2000 0 15.1000 22.2000 24.0000
32.1000 44.8000 34.0000 29.0000 21.7000 15.1000 29.3000 24.3000 15.1000 0 7.1000 39.1000
39.2000 51.9000 41.1000 36.1000 28.8000 8.0000 36.4000 31.4000 22.2000 7.1000 0 45.7000
7.0000 39.8000 30.4000 26.8000 17.4000 37.7000 35.2000 31.5000 24.0000 39.1000 45.7000 0
算法,邻接矩阵C
记C1=C
对k=2 3 4 5 6等，令Ck=Ck-1乘以C
定义：第i行与第j列之元素对应向加之最小值直到有 Ck=Ck-1 为止。
例：此题取自“《运筹学》孔造杰编机械工业出版”第208页第6题。已知邻接矩阵C
，，
注解：元素5表示从到的边权。
，，
略手工计算，以下用机器算。
程序清单：
clear
c=inf*ones(6,6);
for i=1:6
c(i,i)=0;
end
c(1,2)=1;c(1,4)=2;c(2,3)=3;c(2,4)=-1;c(3,4)=5;c(3,6)=2;c(4,5)=-3;c(5,3)=2;c(5,6)=2;
d=c,
for xh=1:10
for i=1:6
for j=1:6
a(i,j)=min(d(i,:)+c(:,j)');
end
end
xhcs=xh+1,d=a
end
执行结果：
C2为
0 1 4 0 -1 Inf
Inf 0 3 -1 -4 5
Inf Inf 0 5 2 2
Inf Inf -1 0 -3 -1
Inf Inf 2 7 0 2
Inf Inf Inf Inf Inf 0
C3为
0 1 1 0 -3 1
Inf 0 -2 -1 -4 -2
Inf Inf 0 5 2 2
Inf Inf -1 0 -3 -1
Inf Inf 2 7 0 2
Inf Inf Inf Inf Inf 0
C4为
0 1 -1 0 -3 -1
Inf 0 -2 -1 -4 -2
Inf Inf 0 5 2 2
Inf Inf -1 0 -3 -1
Inf Inf 2 7 0 2
Inf Inf Inf Inf Inf 0
此时，C3与C4相同，故它就是最后结果。
例：此题取自“《数学实验》刘琼荪编高等教育出版”第193页之图13.3 。已知邻接矩阵C
程序清单：
clear
c=inf*ones(27,27);
for i=1:27
c(i,i)=0;
end
c(1,2)=8.9;c(1,9)=9.8;c(2,3)=9.3;c(2,10)=10;c(3,4)=4.5;c(3,27)=9.6;c(4,5)=3.5;c(4,27)=6.2;c(5,6)=7.7;c(5,12)=9.9;c(6,7)=4.9;c(6,13)=9.5;c(7,8)=6.1;c(7,14)=9.6;c(8,15)=10;c(9,10)=9.8;c(9,17)=13.8;c(10,11)=12.5;c(10,18)=14.2;c(11,12)=3.6;c(11,16)=3.3;c(11,27)=3.7;c(12,13)=7.4;c(12,16)=3.1;c(13,14)=5.0;c(14,15)=7.3;c(15,21)=10.7;c(16,20)=10.4;c(17,18)=10.8;c(18,19)=5;c(18,22)=4.8;c(19,20)=9.4;c(19,23)=4.7;c(20,21)=21.2;c(20,24)=6.6;c(21,26)=8;c(22,23)=5;c(23,24)=9.2;c(24,25)=15.1;c(25,26)=7.1;
d=c,
for xh=1:20
for i=1:27
for j=1:27
a(i,j)=min(d(i,:)+c(:,j)');
end
end
hhh=0;
for ii=1:27
for jj=1:27
hhh=hhh+abs(a(ii,jj)-d(ii,jj));
end
end
if hhh==0
break
end
xhcs=xh+1,d=a
end
执行结果：(迭代计算了9次就发现结果不变了，下面矩阵d的第i行第j列元素即为第i号点到第j号点的最短长度)。
xhcs = 9
d =
Columns 1 through 15
0 8.9000 18.2000 22.7000 26.2000 33.9000 38.8000 44.9000 9.8000 18.9000 31.4000 35.0000 42.4000 47.4000 54.7000
8.9000 0 9.3000 13.8000 17.3000 25.0000 29.9000 36.0000 18.7000 10.0000 22.5000 26.1000 33.5000 38.5000 45.8000
18.2000 9.3000 0 4.5000 8.0000 15.7000 20.6000 26.7000 28.0000 19.3000 13.3000 16.9000 24.3000 29.3000 36.6000
22.7000 13.8000 4.5000 0 3.5000 11.2000 16.1000 22.2000 32.2000 22.4000 9.9000 13.4000 20.7000 25.7000 32.2000
26.2000 17.3000 8.0000 3.5000 0 7.7000 12.6000 18.7000 35.7000 25.9000 13.4000 9.9000 17.2000 22.2000 28.7000
33.9000 25.0000 15.7000 11.2000 7.7000 0 4.9000 11.0000 42.8000 33.0000 20.5000 16.9000 9.5000 14.5000 21.0000
38.8000 29.9000 20.6000 16.1000 12.6000 4.9000 0 6.1000 47.7000 37.9000 25.4000 21.8000 14.4000 9.6000 16.1000
44.9000 36.0000 26.7000 22.2000 18.7000 11.0000 6.1000 0 53.8000 44.0000 31.5000 27.9000 20.5000 15.7000 10.0000
9.8000 18.7000 28.0000 32.2000 35.7000 42.8000 47.7000 53.8000 0 9.8000 22.3000 25.9000 33.3000 38.3000 45.6000
18.9000 10.0000 19.3000 22.4000 25.9000 33.0000 37.9000 44.0000 9.8000 0 12.5000 16.1000 23.5000 28.5000 35.8000
31.4000 22.5000 13.3000 9.9000 13.4000 20.5000 25.4000 31.5000 22.3000 12.5000 0 3.6000 11.0000 16.0000 23.3000
35.0000 26.1000 16.9000 13.4000 9.9000 16.9000 21.8000 27.9000 25.9000 16.1000 3.6000 0 7.4000 12.4000 19.7000
42.4000 33.5000 24.3000 20.7000 17.2000 9.5000 14.4000 20.5000 33.3000 23.5000 11.0000 7.4000 0 5.0000 12.3000
47.4000 38.5000 29.3000 25.7000 22.2000 14.5000 9.6000 15.7000 38.3000 28.5000 16.0000 12.4000 5.0000 0 7.3000
54.7000 45.8000 36.6000 32.2000 28.7000 21.0000 16.1000 10.0000 45.6000 35.8000 23.3000 19.7000 12.3000 7.3000 0
34.7000 25.8000 16.6000 13.2000 13.0000 20.0000 24.9000 31.0000 25.6000 15.8000 3.3000 3.1000 10.5000 15.5000 22.8000
23.6000 32.5000 41.8000 46.0000 48.6000 55.6000 60.5000 66.6000 13.8000 23.6000 36.1000 38.7000 46.1000 51.1000 57.1000
33.1000 24.2000 33.5000 36.6000 37.8000 44.8000 49.7000 55.8000 24.0000 14.2000 26.7000 27.9000 35.3000 40.3000 46.3000
38.1000 29.2000 36.4000 33.0000 32.8000 39.8000 44.7000 50.8000 29.0000 19.2000 23.1000 22.9000 30.3000 35.3000 41.3000
45.1000 36.2000 27.0000 23.6000 23.4000 30.4000 35.3000 41.4000 36.0000 26.2000 13.7000 13.5000 20.9000 25.9000 31.9000
65.4000 56.5000 47.3000 42.9000 39.4000 31.7000 26.8000 20.7000 56.3000 46.5000 34.0000 30.4000 23.0000 18.0000 10.7000
37.9000 29.0000 38.3000 41.4000 42.5000 49.5000 54.4000 60.5000 28.8000 19.0000 31.5000 32.6000 40.0000 45.0000 51.0000
42.8000 33.9000 41.1000 37.7000 37.5000 44.5000 49.4000 55.5000 33.7000 23.9000 27.8000 27.6000 35.0000 40.0000 46.0000
51.7000 42.8000 33.6000 30.2000 30.0000 37.0000 41.9000 48.0000 42.6000 32.8000 20.3000 20.1000 27.5000 32.5000 38.5000
66.8000 57.9000 48.7000 45.3000 45.1000 46.8000 41.9000 35.8000 57.7000 47.9000 35.4000 35.2000 38.1000 33.1000 25.8000
73.4000 64.5000 55.3000 50.9000 47.4000 39.7000 34.8000 28.7000 64.3000 54.5000 42.0000 38.4000 31.0000 26.0000 18.7000
27.8000 18.9000 9.6000 6.2000 9.7000 17.4000 22.3000 28.4000 26.0000 16.2000 3.7000 7.3000 14.7000 19.7000 27.0000
Columns 16 through 27
34.7000 23.6000 33.1000 38.1000 45.1000 65.4000 37.9000 42.8000 51.7000 66.8000 73.4000 27.8000
25.8000 32.5000 24.2000 29.2000 36.2000 56.5000 29.0000 33.9000 42.8000 57.9000 64.5000 18.9000
16.6000 41.8000 33.5000 36.4000 27.0000 47.3000 38.3000 41.1000 33.6000 48.7000 55.3000 9.6000
13.2000 46.0000 36.6000 33.0000 23.6000 42.9000 41.4000 37.7000 30.2000 45.3000 50.9000 6.2000
13.0000 48.6000 37.8000 32.8000 23.4000 39.4000 42.5000 37.5000 30.0000 45.1000 47.4000 9.7000
20.0000 55.6000 44.8000 39.8000 30.4000 31.7000 49.5000 44.5000 37.0000 46.8000 39.7000 17.4000
24.9000 60.5000 49.7000 44.7000 35.3000 26.8000 54.4000 49.4000 41.9000 41.9000 34.8000 22.3000
31.0000 66.6000 55.8000 50.8000 41.4000 20.7000 60.5000 55.5000 48.0000 35.8000 28.7000 28.4000
25.6000 13.8000 24.0000 29.0000 36.0000 56.3000 28.8000 33.7000 42.6000 57.7000 64.3000 26.0000
15.8000 23.6000 14.2000 19.2000 26.2000 46.5000 19.0000 23.9000 32.8000 47.9000 54.5000 16.2000
3.3000 36.1000 26.7000 23.1000 13.7000 34.0000 31.5000 27.8000 20.3000 35.4000 42.0000 3.7000
3.1000 38.7000 27.9000 22.9000 13.5000 30.4000 32.6000 27.6000 20.1000 35.2000 38.4000 7.3000
10.5000 46.1000 35.3000 30.3000 20.9000 23.0000 40.0000 35.0000 27.5000 38.1000 31.0000 14.7000
15.5000 51.1000 40.3000 35.3000 25.9000 18.0000 45.0000 40.0000 32.5000 33.1000 26.0000 19.7000
22.8000 57.1000 46.3000 41.3000 31.9000 10.7000 51.0000 46.0000 38.5000 25.8000 18.7000 27.0000
0 35.6000 24.8000 19.8000 10.4000 31.6000 29.5000 24.5000 17.0000 32.1000 39.2000 7.0000
35.6000 0 10.8000 15.8000 25.2000 46.4000 15.6000 20.5000 29.7000 44.8000 51.9000 39.8000
24.8000 10.8000 0 5.0000 14.4000 35.6000 4.8000 9.7000 18.9000 34.0000 41.1000 30.4000
19.8000 15.8000 5.0000 0 9.4000 30.6000 9.7000 4.7000 13.9000 29.0000 36.1000 26.8000
10.4000 25.2000 14.4000 9.4000 0 21.2000 19.1000 14.1000 6.6000 21.7000 28.8000 17.4000
31.6000 46.4000 35.6000 30.6000 21.2000 0 40.3000 35.3000 27.8000 15.1000 8.0000 37.7000
29.5000 15.6000 4.8000 9.7000 19.1000 40.3000 0 5.0000 14.2000 29.3000 36.4000 35.2000
24.5000 20.5000 9.7000 4.7000 14.1000 35.3000 5.0000 0 9.2000 24.3000 31.4000 31.5000
17.0000 29.7000 18.9000 13.9000 6.6000 27.8000 14.2000 9.2000 0 15.1000 22.2000 24.0000
32.1000 44.8000 34.0000 29.0000 21.7000 15.1000 29.3000 24.3000 15.1000 0 7.1000 39.1000
39.2000 51.9000 41.1000 36.1000 28.8000 8.0000 36.4000 31.4000 22.2000 7.1000 0 45.7000
7.0000 39.8000 30.4000 26.8000 17.4000 37.7000 35.2000 31.5000 24.0000 39.1000 45.7000 0
