陈亮，何为，韩力群

(北京工商大学计算机与信息工程学院，北京 100048)

路径优化是路径规划的核心问题，目前应用最广泛的是1959年Dijkstra［1］提出并以其名字命名的Dijkstra算法，可以解决带有非负代价函数值的路网中的单源最短路径，但是Dijkstra算法的复杂度为O(n2)［2］，由于路径规划要求实时性，因此人们在Dijkstra算法基础上进行各种改进，如进行启发式搜索的A*算法［3］、在记忆路径基础上的启发式搜索算法D*算法［4］等，但是这些算法通常只给出一条最优路径.

本文在路径规划的过程中，利用图的深度优先遍历［5］算法，寻找源点与终点的所有可达路径，并通过限制搜索的路网节点规模和限制搜索方向的规则，进行算法的优化，最后计算得到所有可达路径的代价函数值，并按照从小到大的顺序进行排序.

在将本文的算法应用至实际交通网络中时，为了避免大规模稀疏网络造成计算时间延长，在应用优化的可达路径算法时，将道路网络分成2个级别，得到了较好的效果.利用VC++6.0对算法进行仿真，将未经优化的算法与优化算法的结果进行比较，并用实例验证，表明本文的算法能够很好地实现实时性与最优有效性.

1 可达路径优化算法

1.1 各种存储方式的比较

路径优化问题首先要将实际道路的拓扑结构，通过一定的计算机存储结构进行映射.主要的存储结构形式有邻接矩阵、邻接链表、十字链表、邻接多重链表［6-7］.

邻接矩阵的优势在于容易判断2点间的关系，但缺点是存储稀疏……