文档介绍：空间网络分析
现在学****的是第1页，共46页
网络模型
现在学****的是第2页，共46页
1．网络分析的基本概念
网络是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质沿着路径在空间上的运动。
在GIS中6
6
20
20
0
7
6
20
15
90
8
6
20
20
-90
9
6
20
10
180
7
6
20
0
0
8
6
20
-1
90
9
6
20
-1
-90
9
6
20
-1
-90
7
6
20
5
0
8
6
20
10
90
现在学****的是第13页，共46页
图或网络的存储 P170
邻接矩阵
无向图、有向图 有向网络
1、0 1、&、0
现在学****的是第14页，共46页
3．空间网络分析的方法
路径分析
最短路径分析
连通性分析------最小生成树
中心选址
现在学****的是第15页，共46页
最短路径求解
最短路径求解有多种不同的方法，其中Dijkstra算法适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。
现在学****的是第16页，共46页
例子
20
V5
V0
V4
V1
V3
V2
100
60
30
10
10
50
5
有向网络
现在学****的是第17页，共46页
例子(思路)
A
Ci
Bi
如图所示，A为所求最短距离的起点，其他Bi, Ci 为终点。
目的:求一系列最短距离。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列
步骤:,A到Ci这些顶点的最短距离为无穷大
这就说明A到Ci中的点要么不通，要么通过Bi中的点与之连接。
现在学****的是第18页，共46页
例子(思路)
A
Ci
Bi
这样，对于A到Ci中任何一个点的最小距离，我们总可以在Bi中找到一点，使得A到这一点的最小距离小于前一个距离。（因为A到Ci中的点要么不通，要么通过Bi中的点与之连通。 ）
因此，我们可以先不考虑Ci中的点。
现在学****的是第19页，共46页
例子(思路)
于是，对于右图，我们第一步只考虑下图:
V5
V0
V4
V2
100
30
10
Bi={v2,v4,v5}
20
V5
V0
V4
V1
V3
V2
100
60
30
10
10
50
5
现在学****的是第20页，共46页
例子(思路)
我们用mindist[]这个数组来保存由v0到其它顶点的最小距离，这些距离按升序排列。
考虑右图：
第一步，通过比较，我们知道 mindistance[v0][v2]=mindist[0]=10,（v0-v2)
这是我们求出的第一个最小距离
一旦我们得到v2，我们就可以知道：
V5
V0
V4
V2
100
30
10
向量
现在学****的是第21页，共46页
例子(思路)
V0跟 v2直接连通到的点v3 之间的最小距离不再是无穷大，它应当是mindistance[v0][v2]+dis[v2][v3],
这样我们应当把v3放入前面的集合Bi中。
（注意：有多少v2直接连通到的点都应当考虑进来。）
V5
V0
V4
V3
V2
100
30
10
50
Bi={v2,v4,v5,v3}
现在学****的是第22页，共46页
例子(思路)
第二步，我们把与v2直接连通的点v3考虑进来。
dis[0][5]=100; dis[0][4]=30;
dis[0][2]=10; dis[0][3]=60;
除10以外，30是最小的。
我们可以证明30是v0到其它顶点除10以外最小的。
V5
V0
V4
V3
V2
100
30
10
50
向量
现在学****的是第23页，共46页
例子(思路)
这样我们得到我们的第二个最小距离：
Mindis