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

United Structure of Point-Arc for Network Graph and It's Application in GISs Shortest Path Searching

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

Shortest path analysis is one of the basic problem of GISs network analysis. Algorithm of Dijkstra's and Floyd's are two classic methods, while, to realize them mainly depends on the “adjacency matrix of vertexes”. In this paper, starting from the view of economizing in memory space and increasing operation speed, we use the united structure of point arc to express a map, to realize the justifying and getting the shortest path automatically throuth the algorithm of depth first search. And the practicing method is also given here.