文档介绍：空间网络分析
第1页，共46页，2022年，5月20日，12点35分，星期五
网络模型
第2页，共46页，2022年，5月20日，12点35分，星期五
1．网络分析的基本概念
网络是一个由点、线的二元关系构成的系统，通
9
6
8
7
20
U
型转弯
角度
至弧段
从弧段
结点号
时间阻强
/
s
9
6
8
7
20
高架道或地道
9
6
8
7
20
停靠点
9
6
8
7
20
不准转弯
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页，2022年，5月20日，12点35分，星期五
图或网络的存储 P170
邻接矩阵
无向图、有向图 有向网络
1、0 1、&、0
第14页，共46页，2022年，5月20日，12点35分，星期五
3．空间网络分析的方法
路径分析
最短路径分析
连通性分析------最小生成树
中心选址
第15页，共46页，2022年，5月20日，12点35分，星期五
最短路径求解
最短路径求解有多种不同的方法，其中Dijkstra算法适合于求解某个起点（源点）到网络中的其它各个结点的最佳路径。
第16页，共46页，2022年，5月20日，12点35分，星期五
例子
20
V5
V0
V4
V1
V3
V2
100
60
30
10
10
50
5
有向网络
第17页，共46页，2022年，5月20日，12点35分，星期五
例子(思路)
A
Ci
Bi
如图所示，A为所求最短距离的起点，其他Bi, Ci 为终点。
目的:求一系列最短距离。我们先假定这些最短距离互不相等。那么我们可以把这些最短距离按升序（从小到大）排列
步骤:,A到Ci这些顶点的最短距离为无穷大
这就说明A到Ci中的点要么不通，要么通过Bi中的点与之连接。
第18页，共46页，2022年，5月20日，12点35分，星期五
例子(思路)
A
Ci
Bi
这样，对于A到Ci中任何一个点的最小距离，我们总可以在Bi中找到一点，使得A到这一点的最小距离小于前一个距离。（因为A到Ci中的点要么不通，要么通过Bi中的点与之连通。 ）
因此，我们可以先不考虑Ci中的点。
第19页，共46页，2022年，5月20日，12点35分，星期五
例子(思路)
于是，对于右图，我们第一步只考虑下图:
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页，2022年，5月20日，12点35分，星期五
例子(思路)
我们用mindist[]这个数组来保存由v0到其它顶点的最小距离，这些距离按升序排列。
考虑右图：
第一步，通过比较，我们知道 mindistance[v0][v2]=mindist[0]=10,（v0-v2)
这是我们求出的第一个最小距离
一旦我们得到v2，我们就可以知道：
V5
V0
V4
V2
100
30
10
向量
第21页，共46页，2022年，5月20日，12点35分，星期五
例子(思路)
V0跟 v2直接连通到的点v3 之间的最小距离不再是无穷大，它应当是mindistance[v0][v2]+dis[v