(I．西安文理学院计算机科学系，陕西西安710065；2．华东交通大学信息学院，江西南昌330013)事业。如何能快速的找到两地之间的最短路径，加快交通运a。，计算从点a，到点a．之间的最短路径。常用d，。表示点a。到点a。之间的距离，如果两地间没有通路，则d；l'*，用z’假设点a。可以通过点f1．到达终点a．，点a。到点a；的距足动态规划方法中阶段“无后效性”的限制，在阶段与阶段的空处添加若干个虚结点，对于每个添加的虚结点，使之满足从该虚结点到其后结点的值为原路径的数值，从前一结点到该虚结点的值为0。Zk。(a。)表示从第k阶段的点a．到终点短路径z．。，’-z。‘(a。)．用x。。(a。)表示第k阶段点a。的条件最某交通运输图中有七个结点(如图一所示)，代表七个城市，每个结点间的连线代表两地之闻有通路，其上的数值表示两地之问的距离，如果图中两点问没有连线则说明这两个地区还没有建设通路。袁佳乐1黄兆华2(1．DepartmentScience，Shanxi330013)摘要：随着我国交通运输事业的发展．降低运输成本成为日益关注的问题。动态规划在工程技术、经济管理、工业生产、交通运输等众多领域都有广泛的应用．其中最短路径问题是动态规划在管理领域的一个重要应用。本文通过具体实例说明动态规划在交通运输方面求解最短路径的过程．方法简便，思路清晰。关键词：交通运输：动态规划：最短路径中图分类号：TP31文献标识码：A文章编号：1671—4792一(2008)5一008l-02transportation．Dynamictransportation．ThetransportationimportanceKevwords：Transportation；Dynamic0引言随着国际油价的不断上涨，日益冲击着我国的交通运输输速度，提高服务质量，降低交通运输中的成本，增加经济效益成为运输公司和运输个体经营户关心的问题。在交通运输示意图中(见图一)，有n个结点a，、a，、a，⋯⋯(a；)表示从a。点到终点a．的最短路径。离为d¨从a。点到达终点a。的最短路径为Z’(a；)，则由点a。到达终点的最短路径可表示为z’(a．)=min{d，。q-Z‘(a。))。把网络中的结点按离终点最多的步数划分为k个集合，为满a．的最短路径，可列出方程：z。’(a。)=min{d。．+z。‘(a；))(1)Z。．。’(a)--O(2)其中，i<k,j<k+l。由公式(1)(2)向前递推可得到Z，’(a。)，即是所求的最优点。实例图一交通运输网络示意图1YuanJialeHuangZhaohuaofComputerScience，Xi’anUniversityArtandxi’an701165；2．SchoolInformationEng．，EastChinaJiaotongUniversity，JiangxiNanchangAbstract：Alongwiththedevelopment，peoplereleaseinalreadyapplledprojecttechnique，economymanagement．industryproductiontrafficproblemapplicationfielddynamicprogramming．Thetheoriessearchshortestsystem，theideacleartheoryreliable．Programming；ShortestRoutesystemputattentiontoexpenseprogramminghasispaperroutenloreanuse‘，’％、％。X群拶、厂。州觚hL≮詈’一(习薯l—人“募誊詈o，＼≯，＼A3-A，，消去虚结点得到最优路径A。"3-A，，即所求的A。一r√、v(．眦。饥，4L毗3‘(Ba)--O+ll=lI{。1：、⑤集合x。=“)。它最多四步就可以到达结点A7；在Z4‘(A5)=12+Zs。沁)=12．z4‘(A3)=2+z5‘(A，)---2z2’(A4)铷in，o+z。’(哟=0+20=20z2‘(呦=rain，o屹。‘(B4)=o+12=127+z。‘(Ae)=7+4=11～J各径，交通输z4‘(B。)=4+zs‘(A，)=4x4’=A7上使用z3。(B3)=9+z4‘(A)---9+2=I动态规z3’(A6)铷in／6屹4’(A3)=6+2=8划求解最短路径即Z。‘(A2)=11x2‘_A。Z。’(A1)=ntin，5+Z2‘(A4)=5+11=16得到最优路径的值z。。(A，)=16，此路径通过点A。．A—；3-【1】谢可新．最优化算法【M]．北京：清华大学出版社．⑦集合x3_{运用动态旁劲岛终点～最；个集如图所示将问题