根据“邻接矩阵”计算图(有向无向混合负权均可) 中“从任意一个顶点到任意一个顶点的最短路长” 算法:邻接矩阵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