用矩阵和积求最短路的一种新算法

1、第36卷第9期2006年9月数学的实践与认识Vol.36No.9Sep.,2006用矩阵和积求最短路的一种新算法詹棠森,张三强,唐敏(景德镇陶瓷学院信息工程学院,江西景德333001)摘要:先定义了矩阵和积的概念和运算,在求最短路中,这种方法和线性代数中的矩阵运算相似,通过这种方法,把求最短路转化为矩阵的运算,计算简便,有效.关键词:最短路;矩阵和积;多阶段决策;不完全关联;距离阵1引言求最短路的方法很多,有动态规划的多阶段决策方法1,在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解,而Disjkstra算法是解单源最短路径问题的贪心

2、算法,其基本思想是设置顶点集合S并不断地做贪心选择来扩充这个集合2,3.等.2定义矩阵和积及运算1)符号意义表示和运算表示或运算4,523表示2和32)运算形式和运算律交换律a b=b a分配律a (bc=)(a b)(a c)例2 3=3 2=5,2 (34)=(2 3)(2 4)=56.记 (abc=().3)两矩阵和积的算法设矩阵Am×s=(aij)m×s,Bs×n=(bij)s×nAm×sBs×n=Cm×n=(cij)m×n其中cij=sk=1aik bkj=ai1 b1jais bsj.3构造多阶段决策最

3、短路算法1.完全关联的多阶段问题及距离阵多阶段的决策问题的特点是先将一个复杂问题分解成相互联系的若干阶段,每一个阶段的点(事件点)与后一阶段的点完全相互联系,这种问题称为完全关联的多阶段问题.69期詹棠森,等:用矩阵和积求最短路的一种新算法171如右图1B1C2=7,B1C3=4B2C1=3,B2C3=2B3C1=5,B3C2=1对于四个阶段的决策问题,若第一阶段只有一个点,第二,三,四阶段分别有n,m,1个点.构造矩阵,矩阵的元素由这些距离组成第1,2,3阶段的矩阵为k=A2以kk为列向量构成权矩阵(2)(2)(2)W(2)=(k1,k2,kn)(1)(1)1,k1,k1)=(k(1)(2)

4、(n)T(2)(2)(2)(2)Tkk=(kk1,kk2,kkm),k=1,2,n7.图1W(1)W(s-1)W(s-2)W(2)k.(3)=(k1,k2,km)(3)(3)(3)(3)(1)(s-1)最后得A到T的距离行阵(或称为权阵)k=W(3)W(2)k更一般S阶段的距离为k=2.求A到T的最短路按上图1,利用上面计算权重的方法,可得6k=(6,3,2)7(3)32=(12106,954,1146)42=14128128715810从这些数字中,我们很快找到A到T最短路是7,并按逆推过程可得取得最短路径是AB2C3T,从中可看出距离为8的有3条,距离为10,14,15的各一条,距离为12

5、的有二条.A到T最长距离为15,且路径是AB3C1T.3.其它问题对不完全关联,我们可化不完全关联为完全关联,不是阶段决策问题可化为阶段决策问题.这些问题的转化参考16.在求最小距离时,添加的权记为,在求最大问题时,添加的权记为0.如右图2,实线是已连通,虚线是添加的,且B1C2=4,B2C1=3,B2C3=1,B3C2=8,C1E2=2,C2E3=7,C3E2=10.求A到F的最短路距离.S=(7,8,6)4257963481图2172数学的实践与认识36卷6=(1110,1313,1815)43184=(17161717),1413()1916,()21212219)=(21202121(

6、)1918()2421()24242522从上可得最短路是18,其路径是AB2C1E2F.最长路是25,其路径是AB3C3E2F.同理,对多发点和多收点(即第一阶段和最后阶段有多个点)的情况下,这种算法仍然适用,并且也很简便.在此就不再叙述.参考文献:1运筹学教材编写组编.运筹学M.北京:清华大学出版社,1990.2王晓东编.算法设计与分析M.北京:清华大学出版社,2003.3SaraBaase,AllenVanGelder.ComputerAlgorithmsIntroductiontoDesignandAnalysisM.ThirdEdition,HigherEducationPress,

7、2002.4贺仲雄编.模糊数学及其应用M.天津:天津科学技术出版社,1983.5左孝凌等编.离散数学M.上海:上海科学技术文献出版社,1999.6林同曾主编.运筹学M.机械工业出版社,1989.7姜启源等编.数学模型M.高等教育出版社(第三版),2003.OnaNewAglorithmsofTheShortestPathByMatrix-SumProductZHANTang-sen,ZHANGSan-qiang,TANGMin(SchoolofInformationEngineering,JingdezhenCeramicInstitute,JingdezhenJiangxi333001,China)Abstract:Amatrix-sumproductanditscalculationaredefined,themethodissimilaetocal-culationofmatrixinlinearalgebratosolvetheshortestpath,bythisway,theprocessissi