图的节点-弧段联合结构表示法及其在GIS最优路径选取中的应用

被引：48

作者：

王杰臣

毛海城

杨得志

机构：

[1] 南京师范大学地理系!江苏南京

[2] 南京市建设委员会!江苏南京

[3] 南京大学城市与资源学系!江苏南京

来源：

测绘学报 | 2000年 / 01期

关键词：

地理信息系统; 网络分析; 最短路径分析;

D O I：

暂无

中图分类号：

P208 [测绘数据库与信息系统];

学科分类号：

070503 ; 081603 ; 0818 ; 081802 ;

摘要：

最短路径分析是ＧＩＳ网络分析的一个基本问题，获取最短路径的经典算法主要有迪杰斯特拉（Ｄｉｊｋｓｔｒａ）及弗罗伊德（Ｆｌｏｙｄ）算法，这两种方法的实现都主要借助于图的节点邻接矩阵来表示图并通过适当的搜索技术完成。本文从节约存储空间、提高运算速度出发，采用节点－弧段联合结构来表示图，避开采用大规模数组，并利用深度优先搜索算法，实现最短路径的自动判断与提取，并给出算法的实现方法。

引用

页码：49 / 53

页数：5