首页 | 本学科首页   官方微博 | 高级检索  
     

基于Dijkstra算法的一种最短路径优化算法
引用本文:张福浩,刘纪平,李青元.基于Dijkstra算法的一种最短路径优化算法[J].遥感信息,2004(2):38-41.
作者姓名:张福浩  刘纪平  李青元
作者单位:中国测绘科学研究院,北京,100039
基金项目:国家“十五”重大科技专项课题“中国电子政务空间辅助决策示范工程”支持 (编号 :2 0 0 2BA10 5A -0 1),国家基础测绘项目“政府空间辅助决策系统建设”( 14 60 0 70 3 2 42 11)
摘    要:详细介绍了经典的Dijkstra算法,举例说明了该算法的实现方法以及该算法的缺点:即需要网络结点数平方级的内存;同时详细说明了一种基于Dijkstra算法的优化算法——邻接结点算法,该算法充分利用了网络拓扑信息中的弧段的连接关系,避免了使用含有大量无穷值的关联矩阵,使之更适合带有拐向限制设置的最短路径算法和大量结点的实际数据。实践证明。该算法可以节约大量的内存,对于结点数比较大的网络,或带有大量拐向限制设置的网络,具有较好的适用性。

关 键 词:网络分析  最短路径分析  Dijkstra
文章编号:1000-3177(2004)74-0038-04
修稿时间:2003年3月15日

A New Way of Network Analysis Based on Dijkstra
ZHANG Fu hao,LIU Ji ping,LI Qing yuan.A New Way of Network Analysis Based on Dijkstra[J].Remote Sensing Information,2004(2):38-41.
Authors:ZHANG Fu hao  LIU Ji ping  LI Qing yuan
Abstract:This paper introduces the classical arithmetic of Dijkstra, and it's limitation, which needs geometrical progression memory with increase of network nodes. The paper emphasizes an optimization of shortest path-the algorithm of adjoining nodess, and its improvement, which takes full advantage of the linking relation of arc section in network topology. This avoids conjunction matrix which includes lots of infinitude and suits huge data which includes turning. It is proved that the method can save lots of memory and suit not only huge network but also network of tuning restriction.
Keywords:GIS  network  network analysis  shortest path analysis
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号