摘要
详细介绍了经典的Dijkstra算法 ,举例说明了该算法的实现方法以及该算法的缺点 :即需要网络结点数平方级的内存 ;同时详细说明了一种基于Dijkstra算法的优化算法———邻接结点算法 ,该算法充分利用了网络拓扑信息中的弧段的连接关系 ,避免了使用含有大量无穷值的关联矩阵 ,使之更适合带有拐向限制设置的最短路径算法和大量结点的实际数据。实践证明 ,该算法可以节约大量的内存 ,对于结点数比较大的网络 ,或带有大量拐向限制设置的网络 。
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.
出处
《遥感信息》
CSCD
2004年第2期38-41,共4页
Remote Sensing Information
基金
国家"十五"重大科技专项课题"中国电子政务空间辅助决策示范工程"支持 (编号 :2 0 0 2BA10 5A -0 1)
国家基础测绘项目"政府空间辅助决策系统建设"( 14 60 0 70 3 2 42 11)
