科Ｉ学Ｉ技Ｉ术 Ｄｉｊｋｓｔｒａ算法在实际路径选择巾的应用 李摘要莹郑西彬 陕西・西安７１００６１） （长安大学信息工程学院路网结构复杂，Ｄｉｊｋｓｔｒａ算法查找最优路径时会遍历许多无意义的点，导致算法的执行效率降低，考虑交通状 况等外在因素情况下，查找到的目标路径并非最优。本文在Ｄｉｊｋｓｔｒａ算法的基础上。考虑剔除交通流密度比较大时容 易导致交通堵塞的点，重新搜索路径，从时间和油耗两方面，以交通状况为出发点，对两种情况下算法查找的最优路径 作了对比，从而为人们的日常出行提供参考。 关键词路网拓扑最优路径Ｄｉｊｋｓｔｒａ算法 文献标识码：Ａ 表ｌ 目素 理想路网 ３．ＯＳ ２Ｏ一４０ ４．６９ 中图分类号：ＴＰ３０１ ０引言 Ｄｉｊｋｓｔｒａ锋法的特点是以起始点为中心向外层层扩展，直 实际路同 ４．４ ４Ｓ一５Ｏ ４．０ｌ 到扩展到终点为止。在所有求最短路径的算法中，Ｄｉｊｋｓｔｒａ算 法 沦Ｌ足域叮行的，但是城市交通系统结构复杂，利用Ｄｉ— ｊｋｓｔｒａ算法求最短路径时效率较低。本文以西安市雁塔区的 个 ：域为例，考虑实际交通状况，从出行的经济角度（时间 平ｌＩ￣ｌｌｔ耗）为人们ＦＩ常…行提供了一个 确的参考。 １ Ｄｉｊｋｓｔｒａ算法 １．１理想路网下最优路径分析 传统算法没有考虑路网的实际状况，例如交通堵塞、红绿 法。 １足雁塔 小寨为中心的一部分路网拓扑结构图： 最优路径／ｌｃ 车速分布／ｋ丑／ｈ 百公里耗油／Ｌ 行驶时间／ｍｉｎ ２－１０低速 ２－１—５—９一ｌ０常速 １Ｏ ３９．８６ ／ ／ ８８．２２ 耗泊／ｍｌ 怠遍行￣．Ｓｍｌｎ １０－１２常速 ５３．７５ ８８．２２ ｝ ８８．２２ 总耗油量 ｌ８１．３３ ｌ７６．４４ 从表１可知，理想情况下得…最优路 ２－６．１０—１２，驾乍需 ｌ １分钟。耗油量分析：理想情７兑下最优路径长３．０５ｋｍ，总的 灯以及一些复杂的交通规则。下面以实例来分析Ｄｉｊｋｓｔｒａ算 １０ｍｉｎ，而实际路网中得到的最优路径２—１—５－９ １０ １２，驾乍需 耗油量ｌ８１．３３ｍｌ。实际路网中最优路径长４．４ｋｍ，总的耗油 １７６．４４ｍｌ。就小寨来说，堵车时实际 速小可能达到３０ｋｍ／ｈ， 低速行驶时更费油，怠速转速对油耗也有影响。通常，怠速４ 分钟的油耗相当ｒ以６０ｋｍ／ｈ的时速行驶ｌ公 ｌ 。所以从时 间和油量两方面分析，考虑交通状况后 找的最优路径史符 合人们的实际…行。 ３结论 本文以Ｄｉｊｋｓｔｒａ算法为基础，以雁塔 小寨Ｊ划边为Ｆ１标 域，分别算 了交通畅通和交通堵塞时 １ｉ行驶的最优路径。 从本文分析可知，如果发生交通堵寒，绕仃是一’种ＩｌＪ 行的，Ｊ‘法， 虽然行驶路径距离变Ｋ，但不一定耗油、耗时多，并从时 和 图１ 油量两方面验证了算法最终得到的路径足合理的、仃效的。 参考文献 【１】刘铮，工建昕．汽车发动机原理教程【Ｍ】．清华人学 扳社，２００１． ［２】章永龙．Ｄｉｊｋｓｔｒａ段短路径锋法优化【Ｊ］ｌ南昌工 院学报．２００６，２５（３） 其巾‘６’代表小寨，‘２’是路径起点‘１２’是路径终点，各点 之Ｍ的权值为实际路段的长度。不考虑路网中其它因素时， Ｄｉｊｋｓｔｒａ算法 找的最优路径是２－６．１０—１２（见图１），最优路径 长度为３．０５ｋｍ。 １．２实际路网下最优路径分析 小寨西安ｒ 的核心商业圈，人流量和交通流量都特别大， 所以这个地办会绎常…现交通拥堵，因此在求解最优路径时 町以学虑将这个点剔除，如图ｌ虚线框所示，将‘６’去除，路径 起点仍然为‘２’，终点为‘ｌ２’，各点之间的权值仍然同＿卜。路 网 新遍历 ，Ｄｉｊｋｓｔｒａ算法奁找的最短路径是２－１．５．９—１０－１２， 最 Ｉ 路径长度为４．４ｋｍ。 ２结果分析 考虑红绿灯等凶素的影响，两种情况下查找出最优路 径的Ｉ 行性对比结果如表２所示。 ｌ３８ 一科教导刊ｒ电子版ｊ・２０１４年第５期ｒ下ｊ一
