资源描述：
《最短路问题的位势法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第26卷第9期计算机应用与软件Vol126No.92009年9月ComputerApplicationsandSoftwareSep.2009最短路问题的位势法1,211,2周康高婧同小军1(武汉工业学院数理科学系湖北武汉430023)2(华中科技大学控制科学与工程系湖北武汉430074)摘要给出最短路问题的数学模型,根据线性规划的对偶原理提出了最短路问题的两种位势法。这两种算法的计算思路均为:从确定一个起点势和标准势开始;再用标准势与已确定最短路的顶点势进行比较,按照势的由小到大顺序逐步得到其他顶点的势和路由,每次迭代要更新标准势;直
2、到找到终点的势和路由为止。两种算法采用不同的标准势计算法。一种采用原标准势累加1的更新法,该算法仅适用于正整数费用网络;另一种利用弧割的概念寻找最小标准势来代替原标准势,该算法适用于正费用情形。证明了算法的正确性以及为说明算法的有效性给出了一个算例。最后通过与Dijkstra算法的比较分析了位势法的五条特点,得出结论:位势法是求解最短路问题的有效算法。关键词最短路问题位势法增广链弧割POTENTIALALGORITHMOFSHORTESTPATHPROBLEM1,211,2ZhouKangGaoJingTongXiaojun1(Depa
3、rtmentofMathematicsandPhysics,WuhanPolytechnicUniversity,Wuhan430023,Hubei,China)2(DepartmentofControlScienceandEngineering,HuazhongUniversityofScienceandTechnology,Wuhan430074,Hubei,China)AbstractMathematicmodelofshortestpathproblemisbroughtforward.Twosortsofpotentialal
4、gorithmsofshortestpathproblemarefoundaccordingtodualprincipleoflinearprogramming.Thetwopotentialalgorithmsstartwithmakingsurejumping2offpointpotentialandnormalpotential.Thentocomparenormalpotentialwiththevertexpotentialwhoseshortestpathhasbeenmadesure,tofindgraduallyothe
5、rvertexpotentialandpathoriginaccordingtotheorderofthepotentialfromsmalltobig,andtorenewnormalpotentialineachiterative,toendwhenend2vertexpotentialandpathoriginarefound.Twopotentialalgorithmsusedifferentmethodstocomputenormalpotential.Onemethodisthatformernormalpotentialp
6、rogressivelyplusesone,whichisonlythesamewithpositiveintegercost.Theothermethodistofindminimalnormalpotentialforreplacingformernormalpotentialusingarccutconcept,whichisthesamewithpositivecost.Correctnessofthealgorithmareobtainedandproved.Andanexampleexplainsfeasibilityoft
7、hepotentialalgorithm.Finally,fivevirtuesofthepotentialalgorithmareana2lyzedcomparingpotentialalgorithmwithDijkstraalgorithm.Tocometoaconclusionthatpotentialalgorithmisaneffectualalgorithmtosolveshortestpathproblem.KeywordsShortestpathproblemPotentialalgorithmAugmentingch
8、ainArccut出最短路的站点相邻的站点的信息找到新的站点的最短路,而0引言不去调用较远的站点的信息,这节省了存储空间和计算时间,提高了计算效率。在公交网络的查询系统中,需要查询两站点之间最节省的乘车方式
