摘要
本文采用三种基于图论的算法：迪杰斯特拉（Ｄｉｊｋｓｔｒａ）算法、弗洛伊德（Ｆｌｏｙｄ）算法和矩阵算法来建立一个实际的地理信息管理系统（ＧＩＳ）中寻找任意两点间最短路径的问题，并在系统中加以实现．同时讨论了这几种算法的原理、特点、时间复杂度，同时根据实际情况对上述算法进行了比较和优化．最后，结合本系统的具体情况，针对若干典型问题，如“坐标位置的确定”和“简化地理信息数据的输入工作”等给出了相应的解决办法．系统实现结果表明，优化的算法降低了运行复杂度并减少了系统资源的占用；且系统对底层地理信息透明，便于扩展，具有广泛的应用前景．
Based on graph theory, three algorithms (Dijkstra, Floyd and Matrix) on how to find the shortest path between any two points are discussed in this paper and realized in GIS. On the basis of real situation, the principle, characteristic, time complexity of these algorithms are compared and optimized. In the end of this paper, the solution to check the point in the map and simplify the data input is presented. It is demonstrated that the optimized algorithm can run faster and reduce the complexity. The program is open to endusers, convenient to expand and easy to use.
出处
《上海大学学报（自然科学版）》
CAS
CSCD
1997年第S1期67-70,共4页
Journal of Shanghai University:Natural Science Edition
