文献类型：期刊文章

作　　者：宋巨川[1] 李军[1] 张文俊[1]

机构地区：[1]上海大学通信与信息工程学院信息工程系

出　　处：《上海大学学报（自然科学版）》

年　　份：1997

卷　　号：3

期　　号：S1

起止页码：67-70

语　　种：中文

收录情况：AJ、CAS、CSA、CSA-PROQEUST、CSCD、CSCD_E2011_2012、JST、MR、RCCSE、ZGKJHX、ZMATH、普通刊

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

关 键 词：图论 迪杰斯特拉算法  弗洛伊德算法  地理信息系统

分 类 号：TP301.6]