高速公路网中的Dijkstra最短路径优化算法.pdf

2 2 2
智能交通靳引利等:高速公路网中的 Dijkstra 最短路径优化算法
高速公路网中的 Dijkstra 最短路径优化算法
靳引利1 ,王军2
(1. 长安大学电子与控制工程学院陕西西安 710064 ;2. 陕西省高速公路收费管理中心陕西西安 710021)
摘要:当高速公路网中出现交通事件时,其拓扑结构发生了变化,需要搜索新的最短路径并告知司机。由于信息发布
具有较高的实时性,最短路径的搜索效率对高速公路信息服务的效率有重要影响。论文采用 Dijkstra 算法搜索高速公路网
中的最短路径,并结合高速公路网的特点,用链结构将表示各收费站的点连接起来,简化了高速公路网的拓扑结构,从而大
幅减少 Dijkstra 算法中的节点数。对算法的复杂度分析表明,这种方法大幅减少了路径搜索的复杂度,从而缩短了计算时
间,提高了最2短路2 径搜索效率。
关键词:高速公路网;拓扑结构;Dijkstra 算法;优化
中图分类号: TP18 文献标识码:B 文章编号:1004 373X(2008) 21 188 04
Optimized Dijkstra Shortest Path Algorithm on
J IN Yinli1 ,WAN G J un2
(1. School of Electronic & Control Engineering ,Chang′an University ,Xi′an ,710064 ,China ;
2. Toll Management Center for Highway in Shaanxi Province ,Xi′an ,710021 ,China)
Abstract : Topology of has changed when traffic accident occurred. New shortest path need to be searched
and published to drivers. The efficiency of searching shortest path has important effect on the information service efficiency in
. Combined with the characteristic of ,the paper adopts Dijkstra algorithm in searching shortest
path in ,predigests the topology of and reduces the number of nodes in Dijkstra algorithm by
linking points which represent toll gates by the structure link. Complicacy analysis to the algorithm show that ,this method
decreases plicacy of path searching ,shortens calculating time and promots the efficiency of shor