地理信息系统中建立最短路径的算法

被引：14

作者：

宋巨川 ^{[1
]}

李军 ^{[1
]}

张文俊 ^{[1
]}

机构：

[1] 上海大学通信与信息工程学院信息工程系

来源：

上海大学学报(自然科学版) | 1997年 / S1期

关键词：

图论; 迪杰斯特拉算法; 弗洛伊德算法; 地理信息系统;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

本文采用三种基于图论的算法：迪杰斯特拉（Ｄｉｊｋｓｔｒａ）算法、弗洛伊德（Ｆｌｏｙｄ）算法和矩阵算法来建立一个实际的地理信息管理系统（ＧＩＳ）中寻找任意两点间最短路径的问题，并在系统中加以实现．同时讨论了这几种算法的原理、特点、时间复杂度，同时根据实际情况对上述算法进行了比较和优化．最后，结合本系统的具体情况，针对若干典型问题，如“坐标位置的确定”和“简化地理信息数据的输入工作”等给出了相应的解决办法．系统实现结果表明，优化的算法降低了运行复杂度并减少了系统资源的占用；且系统对底层地理信息透明，便于扩展，具有广泛的应用前景．

引用

页码：67 / 70

页数：4