资源描述：
《基于_矩阵乘法_的网络最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第7期电子学报Vol.37No.72009年7月ACTAELECTRONICASINICAJuly2009基于/矩阵乘法0的网络最短路径算法邓方安,雍龙泉,周涛,刘丽华(陕西理工学院数学系,陕西汉中723001)摘要:网络最短路径问题可以作为许多实际应用问题的模型,但传统的求解算法其迭代过程复杂.本文描述了基于矩阵乘法的最短路算法,其时间复杂度与Dijkstra算法相同.在给定的一个网络图中,在不改变网络图中的最短路的条件下,删除/多余0的结点或边,可以达到简化网络图和提高求解速度的目的,从而降低计算复杂性.最后,研究了该方法在最短路径问题
2、和旅行商问题中的应用.实例表明,这种算法与传统的动态规划技术相比,具有运算简便、易于理解的优点.关键词:矩阵乘法;最短路问题;约简原则;旅行商问题中图分类号:TP30116文献标识码:A文章编号:0372-2112(2009)07-1594-05ShortestPathProblemAlgorithminNetworkBasedonMatrixMultiplicationDENGFang-an,YONGLong-quan,ZHOUTao,LIUL-ihua(DepartmentofMathematics,ShaanxiUniversityo
3、fTechnology,Hanzhong,Shaanxi723001,China)Abstract:ShortestPathProbleminnetworkcanbeactedasamodelformanyapplicationproblems,buttheiterationprocessoftheconventionalsolutionalgeorithmiscomplex.Inthispaper,theshortestpathalgorithmbasedonthematrixmultiplicationinaweighted-graph
4、aredescribed,anditstimecomplexityisassameasDijkstraalgorithm.Inagivennetworkgraph,thisalgorithmdeletesparenodesoredgesandreachthegoalthatreducednetworkgraphandimprovedspeedofsolvingproblemunderthecond-itionofunchangedshortestparth.Finally,wegiveexamples,e.g.TravelingSalesm
5、anProblem,shortestpathproblem,toillistrateitsadvanteges,possessingmeritsofsimpleoperationandeasyunderstanding,comparedwithdynamicprogrammingtechnology.Keywords:matrixmultiplication;shortestpathproblem;reducedprinciple;travelingsalesmanproblems出了时间依赖的网络的定义和模型,给出一种实用反馈1引言式神经
6、网络来求解时间依赖的网络的最短路径问题.并日常生活和生产中许多问题都可以用一个网络来用模拟实验验证了它在不同的网络更新时间区间上收描述.例如,交通网络,计算机网络,工程进度网络,生物敛速度的稳定性.结果是神经网络求解非NP-难解类优[1~4]信息网络和互联网等.对于诸如最短路径问题、最化问题的一种新尝试.本文介绍了基于矩阵乘法运算的小费用问题,最大流问题等经典网络优化问题的解决,最短路算法,并考虑了该算法的时间复杂度,研究了它[5]除了比较成熟的动态规划技术外,一些新的进化算的应用.法,包括蚁群算法、人工神经网络和遗传算法被提[6,7]2算
7、法的描述出.传统的Bellman动态优化算法可以求解最短路问题,但这种算法需要很大的空间,最好和最坏的情况动态规划是求解许多重要应用问题的关键技术,可下的时间差不多相同.虽然它在规模比较小的时候,可以高效地解决许多用贪心算法或分支定界方法无法解以很好的解决问题,但是,随着问题规模的扩大,Bellman决的问题.但该方法比较抽象,难于理解.下面利用/矩动态优化算法就显得无能为力.文献[8]扩展了线性代阵乘积0运算求解最短路问题.不难看出:新方法比动态数中的矩阵运算,定义了矩阵和与积的概念及运算,通规划方法运算简便,容易理解.过这种方法,可以把
8、求最短路转化为矩阵的运算,计算例1图1表示从起点A到终点E之间各点的距简便、有效.文献[10]用实例证明了著名的Dijkstra算法离,求A到E的最短路径.在时间依赖的网络上不能
