浅谈GIS中网络分析与最短路径的实现讲解学习.doc

浅谈GIS中网络分析与最短路径的实现

精品文档
浅谈GIS中网络分析与最短路径的实现
专业：交通信息工程及控制
本科生：程海峰
主导老师：林科
摘 要
网络分析作为GIS的重要功能在电子导航、交通管理、城市规划、管线的布局设计中发挥了重要的作用。本文侧重于从网络拓扑关系的获取到最短路径算法的实现，为进一步研究GIS中网络分析的高效访问奠定基础。
文章首先介绍了网络拓扑数据模型的一些基本概念，根据已有的研究经验，提出了自己有关网络数据模型中最基本的两个概念（网线和结点）的理解。在这个框架之下，又分析了网络拓扑关系的建立过程，得出了网络拓扑关系获取的一般过程。第二部先介绍了最短路径算法选择的有关问题，通过查阅有关文献发现，目前解决系统最短路径问题应用最为广泛的是Dijkstra算法的思想。最后阐述了有关经典Dijkstra算法的主要思想并利用有关数据结构方面的知识写出了具体算法的实现过程。

关键词：网络拓扑 网络数据模型 Dijkstra算法

收集于网络，如有侵权请联系管理员删除
目 录
摘 要 I
1. 引 言 - 1 -
2. 网络拓扑关系的建立 - 2 -
2.1 网络数据模型的基本概念 - 2 -
2.2 网络拓扑关系的获取 - 2 -
3. 最短路径算法 - 5 -
3.1 算法选择 - 5 -
3.2 传统Dijkstra算法的主要思想 - 5 -
3.3 经典Dijkstra算法的实现 - 6 -
参考文献 - 8 -
附 录 - 9 -

1. 引 言
随着地理信息系统产业的建立和数字化信息产品在全世界的普及，地理信息系统已经深入到各行各业。其中，网络分析是地理信息系统（GIS）最主要的功能之一。对地理网络（如交通网络）、城市基础设施网络（如各种网线、电力网线、电话网线、供排水网线等）进行地理分析和模型化，是地理信息系统中网络分析的主要目的。近几年来面向社会的GIS应用开发不断增多,逐渐形成以MapObject和MapGuide为主流的GIS应用开发体系，但这两个系统都没有现成的网络分析功能,只有通过二次开发才能实现MapObject和MapGuide的网络分析功能。 
 网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。其实,无论是距离最短、时间最快还是费用最低,它们的核心算法都是最短路径算法。 
最短路径的求解,必须把现实生活中的道路、管线等各种网络抽象成一种数学结构,这种抽象出来的数学结构被称为网络拓扑结构。于是各种网络分析技术实现的关键在于网络拓扑结构的建立和高效能最短路径算法。下面我就分别从这两方面讨论起。 

2. 网络拓扑关系的建立
网络分析是空间分析的一个重要方面，是依据网络拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连结、联通关系），并通过考察网络元素的空间、属性数据，对网络的性能特征进行多方面的分析计算。对地理网络、城市基础设施网络进行地理分析和模型化的关键技术是用什么样的方式抽象出网络拓扑结构,及节点与节点的连通关系,并对网络拓扑结构进行高效能访问。
2.1 网络数据模型的基本概念
网络是由若干线性实体互连而成的一个系统，资源由网络来传输，实体间的联络也由网络来达成。网络数据模型是真实世界中网络系统（如交通网、通讯网、自来水网等）的抽象表示。构成网络的基本元素是上述线性实体以及这些实体的连结交汇点。前者被称为网线或链（link），后者一般称为结点（node）。网线构成网络的骨架，是资源传输或通讯网络的通道，可以代表公路、铁路、航线、水管、河流等；结点是网线的端点，又是网线的交汇点，可以表示交叉路口、中转站、河流汇合点等。除了上述基本网络元素之外，网络还可能有若干附属元素，如在路径分析中用来表示途径地点的站点；在资源分配中用来表示资源发散地点或资源汇聚地点的中心；对资源传输或通讯网络起阻断作用的障碍等。针对网络分析的需要，作为网络基本元素的网线或结点除自身的常规属性外，还要具有一些特殊属性的数据。比如，为了实施路径分析和资源分配，网线数据应包含正反两个方面上的阻碍度以及资源需求量，而节点数据也应该包含资源需求量。
2.2 网络拓扑关系的获取
GIS中的数据(如道路、管网、水系等)要进行最短路径的计算,就必须首先将其按结点和边的关系抽象为图的结构,这在GIS中称为构建网络的拓扑关系。只有建立了拓扑关系,我们才能进行网络路径分析。在GIS系统拓扑数据结构中，通常具有如下三种重要的拓扑形式：
说明线串如何相连的连通性，即线串是在结点上相互连接的。
多边形是由一系列相连通的线串组成的。
记录多边形的相邻信息已表示拓扑结构的连续性是根据线串的走向，可以决定谁是左多边形。同时，量多变形之所以相邻是因为二者具有共同的边界。
为了能够更好的描述路网拓扑结构的建立过程，首先介绍一下描述路网的基本要素及各要素的属性。
描述路网的基本要素：
点对象：路网中道路和道路的交叉点以及道路的端点。
先对象：用弧或链表示路段，形成路段的基本规则是：道路的所有车道合在一起，两结点之间的部分形成一个路段。
面对像：有路段线围成的封闭区域。
相关路网要素的属性：
路段标识符（用编号表示）
起、终点标识符（用编号表示）
路段名称
路段长度
道路类别
结点表示符号
结点坐标
通常，可以用赋权图来表示路网。具体做法是分别存储点状实体 ——结点，线状实体——两点间的路段，结点和路段的属性信息，以及实体间的拓扑关系（主要是连通性和方向性）。这样从图论的角度看，便将路网转化为一个图。进一步还可以在每一条边上定义权，这样便得到了一个赋权图。从而，确定某两地间的最优路线问题便可以转化为在赋权图上求两点间的最短路径问题。
对于矢量图形的拓扑关系的描述，主要有基于网路的拓扑模型和基于点集拓扑理论的拓扑模型。基于网络的拓扑模型具有直观、结构清晰、互换性强、便于组织存储等优点。路网拓扑关系主要讨论线与线之间的联通性关系，即将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系，在计算机中这种拓扑关系与面无关，拓扑关系中只记录了线与结点的关系，而没有线与面的关系，所以不是完备的拓扑关系。路网拓扑结构主要包括两种对象，结点（Node）对象和边（Link）对象。结点对象主要包括结点序号，结点属性和它附近的相关信息，及与之相连接的编序号；边对象应包括编序号，长度信息，两个端点序号。根据结点对象相连接的边序号和边对象的两个端点序号，就建立了结点之间的连接特性。
路网的拓扑结构的生成主要找出各路段之间的直接连通性，实现算法是找出相应图层中的所有线图元，然后判断任意两线图元是否相交，根据交点和顶点得到结点，根据橡胶关系判断两条边是否直接相连接，再根据相关信息对相应边赋权值，利用拓扑得到的带权图来查询最短路径。拓扑结构的建立过程表示为图2.1的流程图。

图2.1 拓扑关系建立过程流程图

3. 最短路径算法 
由于网络特征的复杂性和问题的不同特征，最短路径的算法也表现出多样性。但总的来说可以按问题的类型、网络特征和实现的算法进行分类，其中最经典，应用最广泛的的还是Dijkstra算法。在实际应用当中，应该根据不同问题的类型选择适合于该问题的算法。
3.1 算法选择
最短路径算法选取的原则一般包括：1.算法速度快；2.算法占用资源少；3.算法稳定性强。据统计，目前提出来的最短路径算法大约有17种，F.BenJiama等人对其中的15种进行了测试，结果显示有三种效果比较好，他们分别是TQQ（graph growth with to queues）、DKA（the Dijkstra’s algorithm with approximate buckets）、以及DKD（the Dijkstra’s implemented with double buckets）。其中TQQ算法的基础是图增长理论，较适合于单点到其他各点的最短距离；后两种算法则都是基于Dijkstra的算法，较适合于计算两点间最短距离。目前多数系统解决最短路径问题采用的是Dijkstra算法为理论基础,只是不同系统对Dijkstra算法采用了不同的实现方法。针对不同的网络特征、应用需求及具体的硬件环境，各种算法在时间复杂度、空间复杂度、实的难易程度等方面各具特色。
3.2 传统Dijkstra算法的主要思想
Dijkstra 算法的基本思路是：假设每个顶点都有一对标号，其中是从起点s到终点j的最短路径长度；则是从s到j的最短路径中s的前一点。求解从s到j的最短路径的算法的基本过程如下：
初始化。起始点设置为：，为空；‚所有其它点：∞，=？；ƒ标记起始点s，计k=s，其它所有点设为为标记的。
检验从所有以标记的点k到其直接连接的标记点j的距离，并设置：

式中，是从点k到j的直接连接距离。
选取下一个点。从所有为标记的结点中，选取中最小的一个i：

点i就被选为最短路径中的一点，并设为以标记的。
找到点i的前一点。从以标记的点中找到直接连接到点i的点，作为前一点，设置：

标记点i。如果所有点以标记，则算法完全退出，否则，记k=i，转到2）在继续。
3.3 经典Dijkstra算法的实现
首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。 迪杰斯特拉算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度

下面为用C语言描叙的迪杰斯特拉算法：
void ShortestPath_DIJ(MGraph G，int v0， PathMatrix &P，ShortPathtable &D) 
{
//用Dijkstra算法求有向图G的v0顶点到其余v的最短路径P[v]及其带权长度D[V] 
//若P[v][w]为true,那么w是从v0到v当前求得最短路径上的点 
//final[v]为true当且仅当v属于s，即已经求得从v0到v的最短路径 
for(v=0；v <G.vexnum；v++) 
{ 
final[v]=false；
D[v]=G.arcs[v0][v]；
for(w=0；w <G.vexnum；w++) 
P[v][w]=false；                            //设置空路径 
if(D[v] <infinity)   
{
P[v][v0]=true；
P[v][v]=true；
}
} 
D[v0]=0;final[v0]=true；
//开始主循环，每次求得v0到某个v定点的最短路径，并且加v入到s集 
for(i=1；i <G.vexnum；i++) 
{  min=infinity；             //infinity是无穷的大数 
for(w=0；w <G.vexnum；w++) 
  if(!final[w]) 
if(D[w] <min)  
{
v=w；
min=D[w]；
}
final[v]=true；
for(w=0；w <G.vexnum；w++)                     //更新当前最短路径和距离
if(!final[w]   &&   (min+G.arcs[v][w]) <D[w]) 
{
D[w]=min+G.arcs[v][w]；
P[w]=P[v];；
P[w][w]=true；   
} 
}
}
参考文献
[1]胡明光、张亮：《GIS网络分析功能的实现》[J], 《科教文汇》2007年9月下旬刊。
[2]Michael N.DeMers.武法东、付宗棠等译: 《地理信息系统基本原理》[M],电子工业出版社，2001年第二版，第45-47页。
[3]张荣梅：《智能交通地理信息系统的设计与实现》[J], 《计算机应用研究》2000年第一期，第97-98页。
[4]王行风、贾凌：《GIS支持下的城市交通网络最短路径研究》[J] ，《计算机与现代化》2005年第四期，第9-12页。
[5]F B ZHAN. 《Three fastest Path Algorithms on Real Road Networks》[J], 《Journal of Geographic Information and Decision Analysis》， 1997，1（2）：56-57。

附 录
下面是一个有关用邻接矩阵实现的一个简单C程序
#include<stdlib.h>
#include<stdio.h>
#define MAX 10
//p[][]:二维数组，存放权值
//n:顶点个数
//d[i]:i距离出发点的最短路径
//path[i]:最短路径上i前面顶点的编号
//s:出发点
void shortestPath(int p[][8], int n, int d[], int path[], int s)
{
//判断出发点有没有邻接点
for(int i=0; i<n; ++i)
if( p[s][i] != MAX)
break;
else if(i == n)
return;
//顶点v是否并入集合S中；
bool isUnion[n];
//初始化
for(int i=0; i<n; ++i)
{
d[i] = MAX;
path[i] = -1;
isUnion[i] = false;
}
//初始化出发点相邻接的顶点距离
for(int i =0; i<n; ++i)
{
if(p[s][i] != MAX)
{
d[i] = p[s][i];
path[i] = s;
}
}
isUnion[s] = true;
d[s] = 0;
//选择最短路径
int min, t;
for(int i=1; i<n; ++i)
{
min = MAX;
for(int j=0; j<n; ++j) //s编号不一定就是0，鄙视思维定势
if(!isUnion[j] && d[j] < min)
{
min = d[j];
t = j;
}
isUnion[t] = true;
//更新t相邻点的值
for(int k=0; k<n; ++k)
{
if(p[t][k] != MAX)
if(!isUnion[k] && d[k] > d[t] + p[t][k])
{
d[k] = d[t] + p[t][k];
path[k] = t;
}
}//for
}//for
}//shortestPath()

/** 打印all路径 */
void printPath(int path[],int n, int d[])
{
for(int i=0; i<n; ++i)
{
int j = i;
printf("到达顶点 %d 的最短长度和路径分别是：%d \n" , i, d[i]);
printf("%d", i);
while(path[j] != -1)
{
printf(" <-- ");
printf("%d", path[j]);
j = path[j];
}
printf("\n");
}
}
/** 测试 */
int main()
{
int s;
int d[8], path[8];
int w[8][8]={
{10, 1, 10,10, 10, 4, 4, 10},
{10, 10, 9, 10, 10, 2, 10, 10},
{10, 10, 10, 1, 10, 10, 10, 10},
{10, 10, 10, 10, 10, 10, 10, 10},
{10, 10, 2, 5, 10, 10, 10, 10},
{10, 10, 6, 10, 3, 10, 3, 4},
{10, 10, 10, 10, 10, 10, 10, 7},
{10, 10, 10, 3, 1, 10, 10, 10}
};
printf("输入起点： \n");
scanf("%d",&s);
//call1
shortestPath(w, 8, d, path, s);
//call2
printPath(path, 8,d);
//display
system("pause");
}