河北地质大学（石家庄经济学院）：《数学软件与实验》课程教学资源（数学建模实验解题）图论之任意两点间的最短路长

根据“邻接矩阵”计算图(有向无向混合负权均可) 中“从任意一个顶点到任意一个顶点的最短路长” 算法:邻接矩阵C 记C 对k=23456等,令Ck=Ck-1乘以C 定义:第i行与第j列之元素对应向加之最小值 直到有Ck=Ck-1为止。 例:此题取自“《运筹学》孔造杰编机械工业出 版”第208页第6题。已知邻接矩阵C 01 2 003-1∞∝ 05 02 注解:元素5表示从v3到v4的边权。 0140-1 0522 CC 2702 略手工计算,以下用机器算。 程序清单 c=inf ones(6, 6) for=1: 6 c(,n)=0; c(1,2)=lc(1,4)=2;c(2,33c(24)=-1c(3,4)=5;c(3,6)=2 c(4,5)=-3c(5,3)=2;c(56)=2 for xh=1: 10 for i=1: 6 a(i,jFmin(d(i, -+c()); d 执行结果: 为 4 Inf03-145 InfInf 0 5 Inf Inf -1 0

根据“邻接矩阵”计算图（有向无向混合负权均可） 中“从任意一个顶点到任意一个顶点的最短路长” 算法： 邻接矩阵 C 记 C1=C 对 k=2 3 4 5 6 等，令 Ck=Ck-1 乘以 C 定义：第 i 行与第 j 列之元素对应向加之最小值 直到有 Ck=Ck-1 为止。 例：此题取自“《运筹学》孔造杰编机械工业出 版”第 208 页第 6 题。已知邻接矩阵 C                                −      −      = 0 2 0 2 0 3 0 5 2 0 3 1 0 1 2 C ，C = C 1 ， 注解：元素 5 表示从 3 v 到 4 v 的边权。 C = C C = 2 1                              − − −    − − −  0 2 7 0 2 1 0 3 1 0 5 2 2 0 3 1 4 5 0 1 4 0 1 ，C C C 3 2 = ， 略手工计算，以下用机器算。 程序清单： 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 70 Inf Inf I C3为 Inf In 0 5 InfInf -1 0-3 Inf Inf 2 70 Inf Int 为 Inf 0 Inf In 0 5 InfInf 0-3 InfInf 2 02 Inf InfInf Ir 此时,C3与C4相同,故它就是最后结果。 例:此题取自“《数学实验》刘琼荪编高等教育出版” 第193页之图13.3。已知邻接矩阵C 程序清单: c=inf°ones(27,27); c(,n) d c(1,2)89c(1,9)98:c(2,3)=93:c(2,10=10;c(34)=4.5 c(3,27)9.6c(45)3.5c(4,27)=62c(5,6)=77c(5,12) 99c(6,7)=4.9c(6,13)}95;c(7,8)=6.1c(714)=96;c(8,1 5=10c(9,10)=9.8c(9,17)=138;c(10,11)=12.5;c(10,18) =142c(1l,12)=36c(11,16=33c(1127)=3.7c(12,13) =7.4c(12,16=3.lc(13,14)=50,c(14,15)=7.3c(1521)= 10.7;c(16,20=10.4c(17,18)=10.8;c(18,19)=5:c(18,22)= 48:c(19,20)=94c(19,23)4.7;c(20,21)=21.2c(20,24) 66;c(21,268c(22,23=5c(23,24)=9.2c(2425)151 c(2526)=7.1; d for xh=1: 20 for i =1: 27 r a(ijF-=min(d(i, )+c(J)); end hh=0; for IF1: 27 for iF1: 27 hhh=hhhtabs(a(ii,j-d(ii, iD

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,1 5)=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));

if hhh==0 break xhcs=xh+l d=a end 执行结果:(迭代计算了9次就发现结果不变了,下面矩阵 d的第i行第j列元素即为第i号点到第j号点的最短长度) Columns 1 through 15 08.900018.200022.700026.200033.9000 38.800044.90009.800018.900031400035.0000 42.400047400054.7000 8.9000 09.300013.800017.300025.0000 29.900036.000018.700010.000022.500026.1000 33.500038.500045.8000 18.20009.3000 04.50008.000015.7000 20.600026.700028000019.300013.300016.9000 24.300029300036.6000 22.700013.80004.5000 03.500011.2000 16.100022200032.200022.40009900013.4000 20.700025.700032.2000 26.200017.30008.00003.5000 12.600018.700035.700025900013.400099000 17.200022.2000287000 33.900025000015.700011.20007.7000 4.900011.000042800033.000020.500016.9000 9500014.500021.0000 38.800029900020.600016.100012600049000 06.100047.700037.900025400021.800014.4000 9.600016.1000 44.900036.000026.7000 200018.7000110000 6.1000 053.800044.000031.5000279000 20.500015.700010.0000 9800018.700028000032.200035.700042.8000 47.700053.8000 09.800022.300025.9000 33.300038.3000456000 18.900010.000019.300022400025.900033.0000 37.900044.000098000 012.500016.1000 23.500028500035.8000 31400022.500013.30009900013.400020.5000 25.400031.500022.300012.5000 03.6000 11.000016.000023.3000 35.000026.100016.900013.40009900016.9000 21.800027.900025900016.10003.6000 74000124000197000 42.400033.500024.300020.700017.200095000 14.400020.500033.300023.50001100007.4000 05.000012.300 47400038500029.300025.700022.200014.5000 9600015.700038.300028.5000160000124000

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.00 07.3000 54.700045800036600032.200028.7000210000 16.100010.000045600035800023.300019.7000 12.30007.3000 0 4.700025.800016600013.200013.000020.0000 24.900031.000025600015.80003.30003.1000 10.500015.500022.8000 500041.800046.000048.600055.6000 60.5000 0013.800023600036.100038.7000 46.100051.100057.1000 33.100024.200033.500036.600037.800044.8000 49700055.800024.000014.200026.7000279000 35.300040.300046.3000 38.100029200036.400033.000032.800039.8000 29.000019.2000 30.300035.300041.3000 45.100036.200027.000023.600023.400030.4000 35.300041400036.000026.200013.700013.5000 20.900025900031.9000 65400056.500047.300042.900039400031.7000 6.800020.700056.300046.500034.000030.4000 23.000018.000010.7000 37.900029000038.300041.400042.5000495000 4400060.500028.800019000031.5000326000 000051 42.800033.900041.100037.700037.500044.5000 .400055.500033.700023.900027.80027.6000 35.0000400000460000 51.700042.80003 30.200030.000037.0000 41900048.000042.6 800020.300020.1000 27.500032.500038.5000 66800057900048700045.300045.100046.8000 41.900035.800057700047.900035.400035.2000 38.100033.100025.8000 73.400064.500055.300050.900047400039.7000 34.800028700064.300054.500042000038.4000 31.000026.000018.7000 27.8000189000960006.20009.7000174000 22.300028400026000016.20003.70007.3000 14.700019700027.0000 Columns 16 through 27 34.700023.600033.100038.100045.100065.4000 37.900042800051.7000668000734000278000 25.800032.500024.200029.200036.200056.5000 29000033.900042.800057.900064.500018.90 16.600041.800033.500036.400027.000047.3000 38.300041.100033.600048.700055.300096000 13.200046.000036.600033.00002360004290 41.400037.700030.200045.300050.90006.2000 13.000048.600037.800032800023.4000394000 42.500037.500030.000045.10004740009.7000

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

000055.600044.800039.8000 400031.7000 49.500044.500037000046.800039.7000174000 24.900060.500049700044.700035.300026800 54.400049400041.900041.900034.800022.3000 31.000066600055.800050.800041400020.7000 60.500055.500048.000035800028.7000284000 25.600013.800024000029000036.000056.3000 28.800033.700042.600057700064.300026.0000 5.800023600014.200019200026.200046.5000 19.000023.900032.800047.900054.5000162000 3.300036.100026.700023.100013.700034.000 31.500027800020.30003540004200003.7000 3.100038.700027.900022.900013.500030.4000 32600027600020.100035200038.40007.3000 10.500046.100035.300030.300020.900023.0000 0.000035.000027.500038.100031.00014.70 15.500051.100040.300035.300025.900018.0000 45.000040.000032.500033.100026.000019.7000 22.800057100046.300041.300031.900010.7000 51.000046.000038.500025.800018.700027.0000 035.600024.800019.800010.400031.6000 29.500024.500017.000032.10003920007.0000 35.6000 010.800015.800025.200046.4000 15600020.500029.700044.800051900039.8000 24.800010.8000 05.000014.400035.6000 4.80009700018.900034.000041.100030.4000 19.800015.80005.0000 09400030.6000 970004.700013.900029000036.100026.8000 10.40002520001440009.4000 021.2000 19.100014.10006600021.700028.800017.4000 31.600046400035600030.600021.2000 40.300035.300027800015.10008.000037.7000 29.500015.60004.80009 19.100040.3000 05000014.200029.300036.400035.2000 24.500020.50009.70004.700014.100035.3000 5.0000 09.200024.300031.400031.5000 17.000029700018.900013.90006.600 278000 14.200092000 015.100022.200024.0000 32.100044.800034.000029000021.700015.1000 29300024.300015.1000 07.100039.1000 39.200051.900041.100036.100028.80008.0000 36.400031400022.20007.1000 0457000 7.000039.800030.400026.8000174000377000 35.200031.500024.000039100045.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