Dijkstra最短路径算法改进研究及应用.doc

Dijkstra最短路径算法改进研究及应用赵雍(陕西省交通规划设计研究院,陕西西安710068)摘要Dijkstra算法是求解最短路径问题的经典算法。但是,在开发交通地理信息系统时,公路线形矢量图中,可能存在大量的折线段,以及大量的端点,如果直接利用此算法构造端点之间的邻接矩阵,要耗费大量宝贵的计算时间和存储空间,从而使其在实际应用中,对求解复杂路线图形的最短路径显得非常困难。针对在实际应用中存在的问题,本文提出了对传统的Dijkstra最短路径算法改进的新方法,即对复杂的公路网数据进行预处理,生成路网拓扑结构数据文件,并结合Dijkstra算法按路径长度递增次序产生最短路径的思想,来解决实际公路网复杂线状图形的最短路径问题。最后,利用VC++语言工具,将这种方法在1:20万陕西省交通地理信息系统中进行实现,证明此方法是准确和高效的。关键词地理信息系统;Dijkstra算法;最短路径;公路网;拓扑关系ImprovementResearchonDijkstraShortestPathAlgorithmandItsApplicationZhaoYong(ShaanxiProvincialTransportPlanningDesignandResearchInstitute,ShaanxiXi’an710068)Abstract:,inpractice,whenwedesignaspecialGeographicInformationSystemforTransportation,,,,inallusiontotheabovequestions,:Ontheonehand,workdata,,,accordingtothisimprovedmethodwedeveloptheGISsoftware—1:200,000scalesShaanxiProvincialGeographicInformationSystemforTransportation—byusingVC++:GeographicInformationSystem;Dijkstraalgorithm;