论文部分内容阅读
目前在GIS领域,对最短路径搜索问题的研究和应用较多,其中最短路径搜索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题,图论中的节点间求解的最短路径问题旨在寻找两个结点问的最短路径。
本文通过对常见的几个有关最短路径算法的分析,即经典的Dijkstra算法、Bellman-Ford算法、Floyd算法等。讨论了各个算法的思想、实现方法、数据结构及算法描述,并从时间和空间的复杂度进行分析比较其优缺点和具体的实用性。针对交通网络本身的特点的分析与研究,介绍了一些适合道路网络的经典最短路径算法和数据存储模式,探讨了在交通网络路线优化过程中需要特别处理的几个问题,并在理论上给出了相应的解决方案。
最后特别针对现代城市交通现状,目前面临着的问题,即城市私家车的增加和城市交通运输的发展,造成交通拥挤、道路阻塞和交通事故正越来越突出等诸多,所以积极发展公交事业尤为重要。而考虑乘客乘车出行实际心理,即尽量缩短时间、缩短路程和缩小费用,最终归结为图论中最短路径问题,即建立-个交通咨询系统,采用图的结构表示实际的交通网络,图中顶点表示站点,边表示站点间的交通联系,该系统用来回答乘客提出查询问题。
本文现以张家口局部路段为例,通过对算法的分析,设计运用Floyd算法,以VC++为设计平台,建立了一个简单城市公交系统,程序调试成功,基本达到了简单查询目的,即实现两站点间的最短路径查询,以方便人们的出行。