智能运输系统(ITS,Intelligent Transportation Systems)是在当代科学技术充分发展进步的背景下产生的,通过将先进的计算机技术、通信技术、现代控制技术运用于交通运输中,协助人们做出最佳的抉择,控制最佳的路网交通。路径诱导系统是智能交通系统的核心部分之一,其重要功能之一是为行驶在道路网中的车辆提供从当前所处位置到目的地的有效、高性能价格比的行车路线,即对交通网络进行路径规划,为行驶车辆提供最佳路径搜索服务。而实现路径引导系统,关键就是解决最短路径搜索问题。 本文针对城市道路网的特点,对基于城市通路网的最短路径分析的关键技术进行了研究。首先系统的介绍了网络分析、图论、地理网络的建模问题等相关理论,接着论述了交通道路刚络在电子地图中的表示。在此基础上论文以图论作为网络分析的主要方法,对城市电子地图的道路网进行网络分析,将最佳路径搜索问题转化为图论中的最短路径搜索问题。 最短路径搜索是图论的经典问题。论文对重点介绍了Dijkstra算法,Floyd算法和启发式搜索算法等几种经典的最短路径搜索算法,对它们之间时间复杂度进行了简单的比较,并针对传统算法的表达方式、存储结构等方面的缺点讨论了最短路径搜索算法的优化方法。以启发式搜索算法为基础,考虑搜索总代价,论文提出了一种寻找最短路径的行之有效的实用算法,使在搜索过程中既不用搜索大量无效节点,又能快速准确地找到两点之间的最短路径。存此基础上提出动态诱导系统的实现方法,并对该系统进行了设计,运用MapX平台开发了一套动态路径诱导的地理信息系统软件,该系统具有直观,人机接口好,能基本满足城市交通诱导的功能。