论文部分内容阅读
Dijkstra算法是求解最短路径问题的经典算法。但是，在开发交通地理信息系统时，公路线形矢量图中，可能存在大量的折线段，以及大量的端点，如果直接利用此算法构造端点之间的邻接矩阵，要耗费大量宝贵的计算时间和存储空间，从而使其在实际应用中，对求解复杂路线图形的最短路径显得非常困难。针对在实际应用中存在的问题，本文提出了对传统的Dijkstra最短路径算法改进的新方法，即对复杂的公路网数据进行预处理，生成路网拓扑结构数据文件，并结合Dijkstra算法按路径长度递增次序产生最短路径的思想，来解决实际公路网复杂线状图形的最短路径问题。最后，利用VC++语言工具，将这种方法在1∶20万陕西省交通地理信息系统中进行实现，证明此方法是准确和高效的。