杜雪 刘卫光

摘 要：首先本文简单概括的论述了传统Dijkstra算法的基本思想；其次提出了该算法在实现方法上存在的一些不足之处，然后从数据存储结构和搜索方式上对其进行优化，并利用Matlab对改进算法进行了相应的仿真分析与测试，结果表明，改进的Dijkstra算法在实际交通中具有可行性。

关键词：智能交通系统；最短路径；Dijkstra算法

中图分类号：TP311.52

针对城市交通拥堵我们提出了智能交通系统，而最短路径算法是智能交通系统最关键的问题之一[1]。目前大家公认的最经典的路径规划算法是Dijkstra算法，它是1959年荷兰著名的科学家艾兹格.迪科斯彻提出来的，并以其名字命名的，它是建立在抽象的图论模型上，把路网抽象为图论中的边，以边的权来表示路网中的相关信息。它也可用来找出图中指定节点到其他节点的最短距离，其主要思想是从源点求出长度最短的一条路径，然后通过对路径长度迭代得到从源点到其他目标节点的最短路径。

如果按照传统的Dijkstra算法，网络图会比较复杂、顶点和边数也会比较多，这样会造成计算量很大、时间开销非常大，从而影响了算法的速度、降低了算法的效率。本文针对Dijkstra算法在实现方法上存在的一些不足之处对其进行改进，改进的Dijkstra算法在实际交通中具有可行性。

1 传统的Dijkstra算法

1.1 算法简单介绍

1.2 算法存在的不足

传统Dijkstra算法虽然比较简单，容易实现，理论上用该算法解决最短路径问题已经很成熟[2]，但是通过仔细分析与研究可知该算法在实际应用中其存在以下几点不足：