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

Optimized Dijkstra Shortest Path Algorithm on Expressway Net

作　　者：靳引利[1] 王军[2] 

机构地区：[1]长安大学电子与控制工程学院,陕西西安710064 [2]陕西省高速公路收费管理中心,陕西西安710021

出　　处：《现代电子技术》2008年第21期188-191,共4页Modern Electronics Technique

摘　　要：当高速公路网中出现交通事件时,其拓扑结构发生了变化,需要搜索新的最短路径并告知司机。由于信息发布具有较高的实时性,最短路径的搜索效率对高速公路信息服务的效率有重要影响。论文采用Dijkstra算法搜索高速公路网中的最短路径,并结合高速公路网的特点,用链结构将表示各收费站的点连接起来,简化了高速公路网的拓扑结构,从而大幅减少Dijkstra算法中的节点数。对算法的复杂度分析表明,这种方法大幅减少了路径搜索的复杂度,从而缩短了计算时间,提高了最短路径搜索效率。Topology of expressway net 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 expressway net. Combined with the characteristic of expressway net, the paper adopts Dijkstra algorithm in searching shortest path in expressway net,predigests the topology of expressway net 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 the complicacy of path searching,shortens calculating time and promots the efficiency of shortest path searching.

关 键 词：高速公路网 拓扑结构 DIJKSTRA算法 优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]