最短路径分析
Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
分类号
密级
编号
2015届本科生毕业论文
题目基于AHP决策分析法和Dijkstra
算法的最短路径
学院资源与环境工程学院
姓名杜玉琪
专业地理科学
学号 205
指导教师王荣
提交日期2015年 5月 8日
原创性声明
本人郑重声明：本人所呈交的论文是在指导教师的指导下独立进行研究所取得的成果。学位论文中凡是引用他人已经发表或未经发表的成果、数据、观点等均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。
本声明的法律责任由本人承担。
论文（设计）作者签名：
指导老师签名：
签名日期: 2013 年 5 月 18 日
目录
基于AHP决策分析法和Dijkstar算法的最短路径分析
——以天水市3A级旅游景点为例杜玉琪(天水师范学院资源与环境工程学院甘肃天水 741000）
摘要：随着西部旅游业的发展，旅游最佳路线的选择变得越来越重要。
本文运用AHP决策分析的方法进行综合评价分析天水市众多旅游景点中
的麦积石窟、伏羲庙、玉泉观、南郭寺、大象山、武山水帘洞、清水温泉，这7个3A级景点各自的旅游价值。再通过Dijkstar算法，对上述
旅游景点的最短旅游路线的选择进行研究，最终为不同要求的游客提供
出最佳的旅游路线。
关键字：AHP决策分析；Dijkstar算法；最短路径分析；天水市
Based on the AHP decision analysis method and the analysis of Dijkstar algorithm of the shortest path
—— in tianshui 3 a-class tourist attractions as an example
Abstract：With the development of the western tourism, tourism optimal route choice is becoming more and more important. This article applies the method of AHP decision analysis on comprehensive evaluation analysis of the numerous tourist attractions tianshui wheat product, yuquan view, nanguo temple grottoes, fu xi temple, the elephant, wushan waterfall cave, water hot springs, the seven aaa scenic spot tourism value. Again through the Dijkstra algorithm, the choice of the tourist attractions of the shortest travel route, finally for different requirements of the best travel route for tourists.
Key words: Analytic hierarchy process; Dijkstar; Shortest path; tianshui city
0 引言
随着西部旅游业如火如荼的发展，天水市自驾旅游开始被越来越多
的人选择。自驾车旅游者追求以最少的花销走更远的路，看更优美的风
景。因此设计出一条多景点间距离最短（或费用，时间最少）的旅游线路是自驾车游客的现实需求[1]。而对于旅游景点的评价及旅游线路的选择问题,是旅游学术界一直关注的课题。众多学者所采用的方法，大体可归纳为主观定性评价和客观定量评价。景点评价方法在我国开展的时间并不长，主要侧重定性描述，较缺乏定量模型研究。定量评价方法分为单项评价和综合评价，综合评价的方法中的“多因素模糊评价法”是近些年发展起来的方法。但由于旅游景点特征具有客观不确定性，在制定评价指标时要考虑到多重因素，不能较好的体现旅游者的不同旅游要求与可得性程度。而AHP决策分析法既能体现定性评价中的旅游者可得性供给程度,也能得出的旅游资源评价指标体系中相关要素按隶属关系从而分为若干层次，再请有经验的专家对各层次各因素的相对重要性给出定量指标，最后利用数学方法综合其权值[2]。为了体现天水历史文化和民俗风情，本文在旅游地选择问题上应用AHP决策分析的方法，最终选择出天水市3A级旅游景点中的7个旅游地。以天水市7个景点旅游路线选择问题为例，通过Dijkstar算法得出天水市自驾旅游的最佳路径。
1 研究区概况
天水作为历史文化名城，位于甘肃省东南部，地处陕、甘、川三省交界，全境介于东经104°35′～106°44′、北纬34°05′～35°10′之间，市区平均海拔高度为1100米。天水历史悠久，文化源深，人文荟萃相传华夏始祖伏羲氏诞生于此，因此又有“羲皇故里”之称[3]。境内交通方便，旅游资源丰富，目前已形成了伏羲文化、秦文化、三国文化、明清建筑文化、民俗风情文化等多元文化景观，其中麦积山石窟作为我国四大石窟之一具有“东方雕塑馆”的美称，周边的风景兼具了江南水乡的秀美和北国山川的雄奇，是国务院公布的第一批风景名胜区。天水人民自古就有祭拜伏羲的习俗，自1988年天水市恢复了公祭伏羲大典,连续多年举办的伏羲祭典，依然成为甘肃和天水重要的对外文化品牌，吸引了众多的海内外华人来天水寻根问祖，祭拜人文始祖。2006
年，太昊伏羲祭典荣列国务院首批国家级非物质文化遗产名录。因此天水市旅游开发的潜力十分巨大。
2.数据来源与研究方法
数据来源
首先从天水旅游统计月报中得到相关数据，并进行研究处理分析得出AHP决策分析中的判断值；其次从goolge电子地图中得出各旅游景点间的最短距离和时间，通过比例尺转化得到旅游景点间具体路径权重值。
研究方法
2.2.1AHP决策分析方法
美国运筹学家T. L. Saaty于20世纪70年代提出的analytic hierarchy process，简称AHP决策分析法，是一种决策者通过对复杂问题的决策思维过程模型化，数量化的方法[7]。应用这种方法，可以把复杂问题划分成若干层次和若干因素，在各因素之间进行简单的比较和计算，就可以得出不同方案重要性程度的权重从而为决策方案的选择提供依据[7]。
（1）AHP决策分析方法的基本步骤：
Step1：明确问题。即弄清问题的范围，所包含的因素以及各因素之间的关系，以便尽量掌握充分的信息。
Step2：建立层次结构模型。即将问题所含的要素进行分组，把每一组作为每一层，并将其按照最高层（目标层），若干中间层（准则层）和最低层（对象层）的次序排列起来。
Step3：构造判断矩阵。判断矩阵表示针对上一层的某元素而言，评定该层次中各有关元素相对重要性程度的判断。
Step4：层次单排序。其目的是对于上层次中的某元素而言，确定本层次与之有联系的各元素重要性次序的权重值。
Step5：层次总排序。利用同一层次中所有层次单排序的结果，就可以计算针对上一层而言，本层次所有元素的重要性权重值。层次总排序需要从上到下逐层按顺序进行，对于最高层而言，其层次单排序的结果也就是总排序的结果。
（2）AHP 决策分析的计算方法（和积法）
Step1：将判断矩阵每一列归一化 1
ij
n
ki
k b b b
==
∑ ()1,2,,i n =
(1)
Step2：对按列归一化的判断矩阵，再按行求和
1n
i ij j W b ==∑ ()1,2,,i n =
(2)
Step3：将向量12(,,,)T i n W W W W =归一化： 1
i
i n
k
k W W W
==
∑ ()1,2,,i n =
(3)
则12(,,,)T i n W W W W =即为所求的特征向量。 Step4：计算最大特征根： max 1()n
i
i i
AW nW λ==∑
(4)
式中：(AW)i 表示向量AW 的第i 个分量。 2.2.2Dijkstra 算法
关于最短路径问题，目前所公认的最好的求解方法，是1959年由着名数学家,Dijkstar 提出的标号法（Dijkstar 算法）[7]。该方法在求解过程的每一个步骤中，都对网络图中的每一个顶点赋予一个相应的数，
这个数就称之为该顶点的标号。这个算法的优点是：首先，它可以求出起点到终点的最短路径及其长度；其次可以求出起点到任何一点的最短路径及其长度；更重要的是它不仅适用于求解有向图上的最短路径问题，而且同样也适用于求解无向图上的最短路径问题[7]。 （1）Dijkstar 算法原理
Dijkstar 算法是计算从某个点到其余各个顶点的最短路径，是按照路径长度递增的次序产生最短路径的算法。
设G=(V,A)是一个赋权有向图，即对于图中的每一条边e=(v i ,v j )，都赋予了一个权值w 。在图G 中指定两个顶点，确定为起点和终点，不妨设v 1为起点，v k 为终点。基本思路是：首先从v 1开始，给每一顶点标一个数，称为标号。这些标号又进一步区分T 标号和P 标号两种类型。其中，每一个顶点的T 标号表示
从起点v 到该点的最短路径长度的上界，这种标号为临时标号；P 标号表示从v 1到该点的最短路径长度，这种标号为固定标号。在最短路径计算过程中，对于已经得到P 标号的顶点，不再改变其标号；对于没有标上P 标号的顶点，先给它一个T 标号；算法的每一步就是把顶点的T 标号逐步修改，将其变为P 标号[7]。那么，最多经过k-1步，就可以求得从起点v 1到每一个顶点的最短路径及其长度。 （2）Dijkstar 算法的基本步骤
Step 1：给v 1标上P 标号P(v 1)=0，对其余各点，均标上T 标号： ()j
V T =+∞ ()1j ≠
(5)
Step 2：如果刚刚得到P 标号的点是v i ，那么，对于所有这样的点v j ：（v i, v j ）E ，而且v j 的标号是T 标号，将其T 标号修改为：min{T(v j ),P(v i )+w ij }。
Step 3：若G 中已经没有T 标号，则停止计算。否则，计算所有T 标号的最小值：
()
()0
0min V j j V T T =
(6)
并将点v jo 的T 标号修改为P 标号，即令P(v jo )=0,然后再转入Step2。 3实例分析
以天水市3A 级旅游景点为例，应用AHP 决策分析方法将旅游地选择问题模型化、数量化。通过对各层次各因素之间的比较和计算，得出不同景点旅游价值的权重，从而为旅游地的选择提供依据，再结合Dijkstar 算法求出各旅游景点的最短路径。 基于AHP 对3A 级景区决策分析 3.1.1层次结构模型的构造
本文确定天水市3A 级旅游景点选择的总目标层（A ），准则层（C ），对象层（P ）三个层次，再根据各因素及其之间的相互关系，可以建立如图1所示的决策层次结构模型。
图1 天水市旅游地选择的层次结构图
Fig1 Tianshui tourism destinations chosen AHP hierarchy structure 每一层中的具体内容如下：
（1）总目标层（A ）——对天水市3A 级旅游景点的选择
（2）准则层（C ）旅游地选择的准则，主要从以下三个方面的准则为判断标准
C
1
——景色优美程度
C
2
——景点消费程度
C
3
——旅行方便程度
（3）对象层（P）：旅游地选择的对象主要包括如下七个方面
P
1
——武山水帘洞
P
2
——大象山
P
3
——玉泉观
P
4
——伏羲庙
P
5
——南郭寺
P
6
——麦积山石窟
P
7
——清水温泉
3.1.2模型计算过程
（1）构造判断矩阵，进行层次单排序。根据上述模型结构，本文构造了A—C判断矩阵和C—P判断矩阵，并进行层次单排序计算，其结果分别如下：
表1 A—C判断矩阵及层次排序结果表
Tab.1 A—C Judgement Matrix and Level Order Result
A C
1C
2
C
3
W
A
排序
C
1
131/32
C
2
1/311/23
C
3
3211从上述表中可以看出，游客在对旅游景点的选择方面最为关注的是旅行方便程度，其次为景点优美程度，最后为景点消费水平。下文则根据游客的心理需求选择出较为合适的旅游景点，从而设计出最佳的旅游路线。
表2 C
1
—P判断矩阵及层次排序结果表
Tab.2 C
1
—P Judgement Matrix and Level Order Result
C
1P
1
P
2
P
3
P
4
P
5
P
6
P
7
W
1
P
1
11/21/31/31/31/41/2
P
2
211/31/31/31/41/2
P
3
3311/221/33
P
4
332131/33
P
5
331/21/311/33
P
6
4433314
P
7
221/31/31/31/41
关数据进行研究，发现麦积山石窟的景色最为优美，伏羲庙、南郭寺、玉泉观、武山水帘洞紧随其后，大象山和清水温泉相对较差。
表3 C
2
—P判断矩阵及层次排序结果表
Tab.3 C
2
—P Judgement Matrix and Level Order Result
C 2P
1
P
2
P
3
P
4
P
5
P
6
P
7
W
1
P
1
11/431/31/21/41/5
P
2
415241/21/3
P
3
1/31/511/41/21/51/7
P
4
344131/21/4
P
5
2221/311/31/5
P
6
4552311/3
P
7
5774551从景点消费水平的角度出发，通过相关数据分析得出：消费水平最高的是清水温泉，其次为麦积山石窟、大象山和伏羲庙，最后为南郭寺、武山水帘洞和玉泉观。
表4 C
3
—P判断矩阵及层次排序结果表
Tab.4 C
3
—P Judgement Matrix and Level Order Result
C
3P
1
P
2
P
3
P
4
P
5
P
6
P
7
W
P
1
1233345
P
2
1/2122234
P
3
1/31/211/21/323
P
4
1/31/2211/234
P
5
1/31/232124
P
6
1/41/31/21/31/214
P
7
1/51/41/31/41/41/41从旅游交通便利的角度出发，通过相关数据分析得出：武山水帘洞和大象山最为便利，其次为南郭寺、伏羲庙和玉泉观，麦积山石窟与清水温泉较为不便利。
（2）层次总排序。根据以上层次单排序的结果，经过总排序计算和一致性检测，得到对象层（P）的层次总排序结果（表5）。
表5 对象层（P）的层次总排序结果表
Final Level Order Results for object(P)
C
1C
2
C
3
W排名
P
1
2
P
2
4
P
3
7
P
4
3
P
5
5
P
6
0,20231
P
7
6
上述表是根据准则层（C）需求通过总排序计算，得出对象层（P）的层次总排序结果：麦积山石窟为最佳旅游地，其次为武山水帘洞、伏羲庙、大象山和南郭寺，玉泉观和清水温泉排名最后。
3.1.3结果分析
通过利用AHP决策分析的方法，对天水市3A级旅游景点的研究，可以得出以下两条基本结论：
（1）从C层的排序的结果来看，天水市3A级旅游地选择的准则应该是，首先考虑旅游出行交通方便程度；其次考虑旅游地景色优美程度；第三考虑旅游地的消费水平。
（2）从P层总排序的结果来看，天水市旅游地选择的优先顺序应该
是：P
6（麦积山石窟）＞P
1
（武山水帘洞）＞P
4
（伏羲庙）＞P
2
（大象
山）＞P
5（南郭寺）＞P
7
（清水温泉）＞P
3
（玉泉观）。
基于Dijkstar算法对3A级景点旅游路线的设计
天水市旅游资源丰富，自驾旅游发展势头强劲。为使其研究样本具有代表性，通过应用AHP决策分析的方法对天水市3A级旅游景点进行分析，最终选定天水市及其周边深受自驾车游客喜爱的七个景点。这个景点为武山水帘洞、大象山、玉泉观、伏羲庙、南郭寺、麦积山和清水温泉。
3.2.1旅游路线模型构造
假定自驾游均以私家车为交通工具，以高速公路和非高速公路为主要道路，车速一定，路况通畅，天气等一切突发情况不纳入考虑范围，同时默认各景点之间回程与去程有多条路径[3]。
3.2.1.1旅游景点赋权图
利用Dijkstar 算法进行旅游线路优化时，需将旅游地图转化为赋权图（图2）。本文对赋权图做了调整，图中只标出线路，具体权值在下文给出。将每个旅游景点看作赋权无向图的一个节点，景点间的交通线路作为边，各景点间的距离、行程时间、交通费用作为对应边的权值，其中各个节点分别代表的旅游景点是：A —武山水帘洞、B —大象山、C —
玉泉观、D —伏羲庙、E —南郭寺、F —麦积山石窟、G —清水温泉。
图2 天水市3A 级旅游景点网络图
Tianshui 3A-class tourist attractions network diagram
3.2.1.2旅游景点线路权值 （1）距离权值
利用ARCGIS 软件，首先将景点间的线路进行数字化处理，其次通过舍远取近的方法找出最短线路，最后利用比例尺转化得到旅游景点间具体距离。从而得出距离权值表（表6），但要注意权值表中的距离只考虑各景点之间的距离，而景区内的距离未列入考虑范围。 表6 旅游景点间路程间距表/㎞
Tourist attraction in the distance between the right
value/km 景点 A B
C
D
E
F
G
A 0
B
D06
E0
F0
G0（2）时间权值
在文中假定车速一定，路况良好，可由各旅游景点间的实际距离计算出其交通时间，从而将时间最短问题表现为具体路径问题。最终绘出时间权值表（表7），但要注意权值表中的时间只考虑各景点之间的交通时间，而景区内的游玩时间未列入考虑范围。
表7 旅游景点间驾车时间表/min
Driving time weight table between tourist attractions/min
景点A B C D E F G A0788292320
B0696766
C021566134 D015
E067133 F0146 G0（3）费用权值
本文按照高速公路车费元/车·㏎及燃油费元/车·㏎的标准计算，将无形的费用问题转化为具体路径问题。先根据旅游景点间的线路分别计算出所需的交通费用，再结合化费用最少的原则确定线路，最终得出费用权值表（表8）。
表8 旅游交通费用表/元
Tourist traffic cost weight table/yuan
景点A B C D E F G A015303035
B0202020
C0581530 D08
E01530 F030 G0 3.2.2模型计算与分析
利用上述旅游景点间距离、驾车时间、交通费用等数据，通过Dijkstra算法，最终设计出旅游路线结果如下。
（1）最短路程路线
当不考虑交通费用与时间，只考虑最少驾车路程时，最佳旅游线路是：A→B→D→C→E→F→G，相对应的线路是：武山水帘洞→大象山→伏羲庙→玉泉观→南郭寺→麦积山石窟→清水温泉。
（2）最省时间路线
当不考虑交通费用和路程，只考虑所用驾车时间最少问题时，最佳旅游线路是：A→B→D→C→E→F→G，相对应的线路是：武山水帘洞→大象山→伏羲庙→玉泉观→南郭寺→麦积山石窟→清水温泉。
（3）费用最少路线
当不考虑时间和路程，只考虑交通费用最少问题时，最佳旅游线路是：A→B→C→D→E→F→G，相对应的线路是：武山水帘洞→大象山→玉泉观→伏羲庙→南郭寺→麦积山石窟→清水温泉。
最终将这三个方面进行综合研究分析，得出游客出行的最佳路径为：武山水帘洞→大象山→玉泉观→南郭寺→麦积山石窟→清水温泉。4结语
将AHP决策分析法和Dijkstar算法应用到旅游路线设计中，所设计
的线路满足游客的需求，方案具有简易性和实用性。随着旅游业的发
展，可建立全国最优旅游路径网站或旅游线路查询决策系统。在掌握控
制旅游业的流量和流向方面，旅游路线的开发和完善起着至关重要的作用。因此，相关技术方法可扩展到区域旅游交通规划和景区内道路设计
等实际应用方面，可跟据实际需要进行改进为旅游相关部门提供决策支持。据此最优路径制定的旅游开发战略可推动沿线地区旅游业的进步，
对区域经济的发展具有深远意义[4]。
参考文献
[1]滕聪,曹文.旅游景点筛选组合及旅游线路的优化算法与应用[J]. 地
球信息科学学报,2010,12(5):668-673
[2]王宁.风景区旅游景点的综合评判及最优旅游路线的选择[J].宁德师
专学报,2003,15(2): 148-152
[3]芦维忠,冉福祥,陈春叶. 天水市旅游信息系统的设计与实现[J]. 测
绘与空间地理信息,2012,11:74-79
[4]樊守伟, 严艳, 张少杰, 田泽民. Dijkstar算法与旅游路径优化[J]. 西安邮电大学学报,2014,19(1):121-124
[5]徐淑梅,吕华健,沈和江.黑龙江省冰雪旅游开发战略AHP决策分析[J]. 人文地理,2008,1: 107-110
[6]王荣,江东,韩惠.基于Floyd方法的最短路径算法优化算法[J]. 甘肃科学学报,2012, 24(4):110-114
[7]徐建华.计量地理学[M]. 北京:高等教育出版社,2012
[8]徐永斌,王斐然.基于多因素模糊综合评价的最优旅游线路分析[J].
湖北民族学院学报,2014,32(1):81-84
最短路径分析（源码） using System; ArcEngine using ESRI.ArcGIS.Carto; using ESRI.ArcGIS.Geometry; using ESRI.ArcGIS.Geodatabase; using https://www.doczj.com/doc/7e10774528.html,workAnalysis;//12 namespace GisEditor { ///
随着计算机和地理信息科学的发展,地理信息系统因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,通用的网络分析功能包括路径分析、资源分配、连通分析、流分析等。网络分析中最基本和最关键的问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位。 从道路网络模型的角度看,最短路径分析就是在指定道路网络的两节点间找出一条阻碍强度最小的路径。根据阻碍强度的不同定义,最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。因此,城市道路网作为一种大型网络设施有其本身的特征。它一方面包含网络本身的拓扑特征;另一方面还包含了大量反应地理位置特征的几何数据。本文根据道路网的特点,运用GIS网络分析功能对道路网络模型、道路的权重选择以及快速寻求路网中两节点间的最短路径算法分别进行了研究。 1 道路网模型及权重设置 1.1 道路网模型建立 城市道路网主要由众多道路相交、相连构成。在纵横交织、错综复杂的道路网络中,道路间的地理位置关系相当复杂,一条道路可能与若干条道路相交相连,且其相交相连的模式复杂。为了避免过多地考虑道路间的拓扑关系,抽取道路网中道路交叉路口作为分析对象,并对道路以交叉路口为结点进行分割,成为路段。这样,整个网络图将由交叉路口点和路段组成,并定义交叉路口点为网络的结点,路段为网络的弧。从而建立基于路段连接的网络模型,其模型形式表述为: 式中,RW代表道路网络;N代表结点集;R代表路段集合,其元素为有序对,表示由结点x到结点y存在一条有向通路;LR代表路段长度集合,其元素表示有向路段的加权长度。其中,路段的加权长度是指根据目标函数要求,综合各种动态实时信息和静态属性信息后所得的路段参数,而并非真实意义下的长度。 1.2 道路网权重选择 在交通路网中,两点间最优路径算法的优劣主要受到2个因素的影响,即所使用的最短路径算法和所选择的道路权重。最短路径算法是路径选择的搜索工具,决定了如何在庞大的路网数据库中找到最佳的可行路径。道路权重则是路径选择的搜索指标,是最短路径算法的依据。因此,道路权重的选择直接影响到最优路径算法的合理性。
ArcGIS空间分析工具（SpatialAnalystTools） 1空间分析之常用工具 空间分析扩展模块中提供了很多方便栅格处理的工具。其中提取（Extraction）、综合（Generalization）等工具集中提供的功能是在分析处理数据中经常会用到的。 1.1提取（Extraction） 顾名思义，这组工具就是方便我们将栅格数据按照某种条件来筛选提取。 工具集中提供了如下工具： ExtractbyAttributes：按属性提取，按照SQL表达式筛选像元值。 ExtractbyCircle：按圆形提取，定义圆心和半径，按圆形提取栅格。 ExtractbyMask：按掩膜提取，按指定的栅格数据或矢量数据的形状提取像元。 ExtractbyPoints：按点提取，按给定坐标值列表进行提取。 ExtractbyPolygon ExtractbyRectangle ExtractValuestoPoints：按照点要素的位置提取对应的（一个/多个）栅格数据的像元值，其中，提取的Value 可以使用像元中心值或者选择进行双线性插值提取。 Sample：采样，根据给定的栅格或者矢量数据的位置提取像元值，采样方法可选：最邻近分配法（Nearest）、双线性插值法（Bilinear）、三次卷积插值法（Cubic）。 以上工具用来提取栅格中的有效值、兴趣区域点等很有用。 1.2综合 这组工具主要用来清理栅格数据，可以大致分为三个方面的功能：更改数据的分辨率、对区域进行概化、对 区域边缘进行平滑。 这些工具的输入都要求为整型栅格。 1.更改数据分辨率 Aggregate：聚合，生成降低分辨率的栅格。其中，CellFactor需要是一个大于1的整数，表示生成栅格的像 元大小是原来的几倍。 生成新栅格的像元值可选：新的大像元所覆盖的输入像元的总和值、最小值、最大值、平均值、中间值。
分类号 密级 编号 2015届本科生毕业论文 题目基于AHP决策分析法和Dijkstra 算法的最短路径 学院资源与环境工程学院 姓名杜玉琪 专业地理科学 学号20111040205 指导教师王荣 提交日期2015年5月8日
原创性声明 本人郑重声明：本人所呈交的论文是在指导教师的指导下独立进行研究所取得的成果。学位论文中凡是引用他人已经发表或未经发表的成果、数据、观点等均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。 本声明的法律责任由本人承担。 论文（设计）作者签名： 指导老师签名： 签名日期: 2013 年 5 月18 日 目录
0 引言 (3) 1 研究区概况 (4) 2.数据来源与研究方法 (4) 2.1数据来源 (4) 2.2研究方法 (5) 2.2.1AHP决策分析方法 (5) 2.2.2Dijkstra算法 (6) 3实例分析 (7) 3.1 基于AHP对3A级景区决策分析 (7) 3.1.1层次结构模型的构造 (7) 3.1.2模型计算过程 (8) 3.1.3结果分析 (10) 3.2基于Dijkstar算法对3A级景点旅游路线的设计 (10) 3.2.1旅游路线模型构造 (10) 3.2.2模型计算与分析 (13) 4结语 (13) 参考文献 (14) 致谢 (15) 基于AHP决策分析法和Dijkstar算法的最短路径分析
——以天水市3A级旅游景点为例 杜玉琪 (天水师范学院资源与环境工程学院甘肃天水741000） 摘要：随着西部旅游业的发展，旅游最佳路线的选择变得越来越重要。本文运用AHP决策分析的方法进行综合评价分析天水市众多旅游景点中的麦积石窟、伏羲庙、玉泉观、南郭寺、大象山、武山水帘洞、清水温泉，这7个3A级景点各自的旅游价值。再通过Dijkstar算法，对上述旅游景点的最短旅游路线的选择进行研究，最终为不同要求的游客提供出最佳的旅游路线。 关键字：AHP决策分析；Dijkstar算法；最短路径分析；天水市 Based on the AHP decision analysis method and the analysis of Dijkstar algorithm of the shortest path ——in tianshui 3 a-class tourist attractions as an example Abstract：With the development of the western tourism, tourism optimal route choice is becoming more and more important.This article applies the method of AHP decision analysis on comprehensive evaluation analysis of the numerous tourist attractions tianshui wheat product, yuquan view, nanguo temple grottoes, fu xi temple, the elephant, wushan waterfall cave, water hot springs, the seven aaa scenic spot tourism value. Again through the Dijkstra algorithm, the choice of the tourist attractions of the shortest travel route, finally for different requirements of the best travel route for tourists. Key words: Analytic hierarchy process; Dijkstar; Shortest path; tianshui city 0 引言 随着西部旅游业如火如荼的发展，天水市自驾旅游开始被越来越多的人选择。自驾车旅游者追求以最少的花销走更远的路，看更优美的风景。因此设计出一条多景点间距离最短（或费用，时间最少）的旅游线路是自驾车游客的现实需求[1]。而对于旅游景点的评价及旅游线路的选择问题,是旅游学术界一直关注的课题。众多学者所采用的方法，大体可归纳为主观定性评价和客观定量评价。景点评价方法在我国开展的时间并不长，主要侧重定性描述，较缺乏定量
最短路径之Dijkstra算法详细讲解 １最短路径算法 在日常生活中，我们如果需要常常往返A地区和B 地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法
有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２Dijkstra算法 2.1 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 2.2 Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。 2.3 Dijkstra算法具体步骤 （1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u 的距离值，修改后的距离值的顶点k的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。 2.4 Dijkstra算法举例说明 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）
电力线路设计中线路路径选择问题及措施分析 摘要：输电线路的路径选择直接关系到电能传送的质量以及效率，同时对电网 的整体稳定运行也有一定的影响，所以无论什么时候都必须重视输电线施工中对 路径的选取。本文综合阐述了输电线在路径选择遵循的基本原则以及在特殊条件 之下如何进行路径的选择，对于选择中出现的问题有针对性的提出解决措施，只 有这样才能保证输电线的抗干扰能力，进而保证电网的稳定运行。 关键词：电力线路；路径选择；基本原则；问题探究 引言 电力线路设计中路径的选择应综合气候、地形、地质、地貌等条件加以衡量，确保线路选择具备经济性、稳定性等原则。其次，对于杆塔的选择也应综合分析。采用合理、经济、运维简便等理念，满足电网技术先进合理，安全有效。促进现 代电网安全运行。 1电力线路路径设计现状 近年来，供电需求不断增加，新建线路不断服役，与已有不同电压等级的电 力线路相交融，造成新旧电力线路混合在一起，对于整个电力走廊的规划起着制 约作用，并出现了很多显著的设计电力线路路径问题：（1）很多电力线路路径 设计时受已有及规划设施的影响和走廊的制约存在绕远的状况，造成了很大程度 上的电能浪费和线路本身的投资增加。（2）电力线路网络结构缺乏科学性，很 多地方只是简单进行线路规划，但新老电力线路更替时打乱了线路规划，造成电 力线路网络结构太复杂，管理难度随之提高。（3）电力线路设计人员在设计电 力线路中，没有实地深入考查有关条件，造成电力线路设计流程太简单，对影响 因素没有考虑周全，如没有对当地地质与气候情况对布设线路带来的影响进行综 合分析和考虑。在接受任务之后，就需要严格考查沿途地貌地形，尤其应充分结 合电力系统的整体供电规划，不但考虑当前供电需求，还要兼顾远期线路改造接 入的可能性和便利性。电力线路路径设计中存在的上述问题，制约着配电网整体 配电能力的提高，需要妥善解决。 2电力线路设计路径选择基本原则 一般来说，输电线路在路径的选择上受到两个因素的制约，其中第一个因素 是技术方面的因素，第二个因素是经济方面的因素，换句话说就是完成线路的路 径选择所需要最少的成本。除此之外，线路在路径的选择上还需要综合的顾及后 期的维护与保养，同时对于选择的路径之后不能对当地的建筑等造成一定的威胁。基于上述的论述，电力线路的路径在选择的时候依照的基本原则可以被归纳为以 下四个指标。第一个指标是把实际的施工中所遇到的问题同上述的两个制约因素 相互融合，从而在实现后期简单维护的基础之上，能够合理的完成施工任务；第 二个指标是尽可能的选择地势良好的路径，不能出现较大的转弯路径，同时尽可 能的躲避悬崖、较宽的水域等环境；第三个指标是在路径的选择过程中绕开居民 住宅区、高层建筑物、茂密的森林和绿化设施等，这样一来能够保障线路的通畅；第四个指标是如果上述的指标不能同时的实现，那么在选择路径的时候要选择最 短的路径设计，同时使得周围的环境对输电线路的干扰降低到最小。 3电力线路设计中线路路径选择问题探究 3.1电力线路设计 电力路径的选择中常分为两个方面，即野外选线、图上选线。其中，实际工 作的主要内容包括：根据实际情况设计若干路径方案，再收集有关资料开展野外
综合实习7：最短路径问题分析与应用 1．背景 在现实中，最短路径的求取问题可以拓展为许多方面的最高效率问题，最短路径不仅指一般意义上的距离最短，还可以是时间最短、费用最少、线路利用率最高等标准。 2．目的 学会用ArcGIS10进行各种类型的最短路径分析，理解网络分析原理。 3．数据 GeoDatabase地理数据库：City.mdb。 数据库中包含一个数据库：City，其中含有城市交通网net、商业中心及家庭住址place、网络节点city_Net_Junctions等要素。 4．要求 根据不同的要求，获得到达指定目的地的最佳路径，并给出路径的长度；找出距景点最近的某设施的路径。 在网络中指定一个商业中心，分别求出在不同距离、时间的限制下从家到商业中心的最佳路径。 给定访问顺序，按要求找出从家出发，逐个经过访问点，最终到达目的地的最佳路径。 研究阻强的设置对最佳路径选择的影响。 5．操作步骤 启动ArcMap，打开city.mdb，双击city数据库，加载数据。 对点状要素place符号化：以HOME字段，1值为家，0值为商业中心。 （1）无权重最佳路径的生成 1）在几何网络分析工具条上，选择旗标工具，将旗标放在“家”和想要取得“商业中心”点上。 2）选择分析|选项命令，打开“分析选项”对话框，确认“权重”和“权重过滤器”标签项全部是“无（None）”，这种情况下进行的最短路径分析是完全按照这个网络自身的长短来确定。 3）在“追踪任务”文本框中选择“网络路径分析”。单击“解决”按钮。显示出最短路径（图7-1），这条路径的总成本显示在状态栏中。
图7-1 无权重参照的最短路径的显示 （2）加权最佳路径生成 1）在几何网络分析工具条上，点选旗标工具，将旗标分别放在“家”和想去的某个“商业中心”的位置上。 2）选择“分析|选项”命令，打开“分析选项”对话框（图7-2）进入“权重”标签页，在边的权重（Edge weights）上，全部选择长度（length）权重属性。 图7-2 长度权重属性设置
兰州交通大学开放性实验 基于ArcGIS的地理分析 实 验 报 告 实验名称：矢量数据的空间分析-以最短路径分析为例 学生姓名：张鑫港 学生学号：201408301 指导老师：朱睿 时间：2016年5月1日 1.实验背景 最短路径的分析问题在现实生活中有着广泛的应用，可以有助于提高效率，减少资源的消耗，故对最短路径的研究有着重要的意义。
2. 实验目的 通过本练习，掌握ArcGIS最短路径分析的方法，深入理解网络分析的原理。 3. 实验要求 通过分析能够得到到达指定目的地的路径选择方案及根据不同的权重得到不同的最佳路径，并给出路径的长度（总成本）。 （1）在网络中指定一个点，分别求出在不同距离、时间的限制下从指定的另一点到此点的最短路径。 （2）给定访问顺序，按要求找出逐个经过中间位置最终到达目的地的最佳路径。 （3）研究阻抗的设置对最佳路径选择的影响。 4. 实验操作步骤 1）无权重最佳路径的选择 无权重最短路径，即说明路径的长短是此网络分析的唯一标准。 此时计算出的是距离上最短的路径，左下角显示出此网络的总成本，本例中显示为20，即为总共经过20个路口的含义。（以下图中都可显示总成本，不再一一说明） 2）加权最佳路径的选择 加权最佳路径的选择，可以是距离、时间、速度等的加权，要根据分析的具体情况决定以何属性加权。以下以时间加权与距离加权为例说明。
时间加权 距离加权 加权的意义，既为网络分析提供分析依据，即以何作为计算因素来进行分析。 3）按要求和顺序能够逐个通过目标点的路径的实现 如果在一个网络分析中按照一定的顺序依次标定所要经过的点位，此时可以同时赋予权重（本图中以距离权重为例），则可以得到按指定顺序行进的最优路径。 4）阻强问题 权重是通过边线或连接的成本，它只能基于长整型或双精度型数据类型创建。在本例 阻强问题指的是点状要素或线状要素因为某些突发事件而不可运行时，原先获取的最优路径就可能会被修正。本例中同时设置了点要素障碍与边要素障碍，可以看出设置阻碍后最优路线的修正。
空间分析复习提纲 一、基本概念(要求：基本掌握其原理及含义，能做名词解释) 1、空间分析：是基于地理对象的位置和形态的空间数据的分析技术，其目的在于提取和传输空间信息。 2、空间数据模型：以计算机能够接受和处理的数据形式，为了反映空间实体的某些结构特性和行为功能，按一定的方案建立起来的数据逻辑组织方式，是对现实世界的抽象表达。分为概念模型、逻辑模型、物理模型。 3、叠置分析：是指在同一地区、同一比例尺、同一数学基础、不同信息表达的两组或多组专题要素的图形或数据文件进行叠加，根据各类要素与多边形边界的交点或多边形属性建立多重属性组合的新图层，并对那些结构和属性上既互相重叠，又互相联系的多种现象要素进行综合分析和评价；或者对反映不同时期同一地理现象的多边形图形进行多时相系列分析，从而深入揭示各种现象要素的内在联系及其发展规律的一种空间分析方法。 4、网络分析：网络分析是通过研究网络的状态以及模拟和分析资源在网络上的流动和分配情况，对网络结构及其资源等的优化问题进行研究的一种空间分析方法。 5、缓冲区分析：即根据分析对象的点、线、面实体，自动建立它们周围一定距离的带状区，用以识别这些实体或主体对邻近对象的辐射范围或影响度，以便为某项分析或决策提供依据。其中包括点缓冲区、线缓冲区、面缓冲区等。 6、最佳路径分析：也称最优路径分析，以最短路径分析为主，一直是计算机科学、运筹学、交通工程学、地理信息科学等学科的研究热点。这里“最佳”包含很多含义，不仅指一般地理意义上的距离最短，还可以是成本最少、耗费时间最短、资源流量（容量）最大、线路利用率最高等标准。 7、空间插值：空间插值是指在为采样点估计一个变量值的过程，常用于将离散点的测量数据转换为连续的数据曲面，它包括内插和外推两种算法。，前者是通过已知点的数据计算同一区域内其他未知点的数据，后者则是通过已知区域的数据，求未知区域的数据。 8、空间量算：即空间量测与计算，是指对GIS数据库中各种空间目标的基本参数进行量算与分析，如空间目标的位置、距离、周长、面积、体积、曲率、空间形态以及空间分布等，空间量算是GIS获取地理空间信息的基本手段，所获得的基本空间参数是进行复杂空间分析、模拟与决策制定的基础。 9、克里金插值法：克里金插值法是空间统计分析方法的重要内容之一，它是建立在半变异函数理论分析基础上，对有限区域内的区域变化量取值进行无偏最优估计的一种方法，不仅考虑了待估点与参估点之间的空间相关性，还考虑了各参估点间的空间相关性，根据样本空间位置不同、样本间相关程度的不同，对每个参估点赋予不同的权，进行滑动加权平均，以估计待估点的属性值。 二、分析类(要求：重点掌握其原理及含义，能结合本专业研究方向做比较详细的阐述) 1、空间数据模型的分类？ 答：分为三类： ①场模型：用于表述二维或三维空间中被看作是连续变化的现象； ②要素模型：有时也称对象模型，用于描述各种空间地物； ③网络模型：一种某一数据记录可与任意其他多个数据记录建立联系的有向图结构的数据模型，可 以模拟现实世界中的各种网络。
网络分析（最短路径问题分析） 一、实验目的： 理解最短路径分析的基本原理，学习利用arcgis软件进行各种类型的最短路径分析的操作。 二、实验准备 1、实验背景： 最短路径分析是空间网络分析中最基本的应用，而交通网络中要素的设置对最短路径的选择有着很大的影响。实验要求根据不同的权重，给出到达指定目的地的路径选择方案，并给出路径长度。 在网络中指定一个超市，要求分别求出在距离、时间限制上从家到超市的最佳路径。 给定访问顺序，按要求找出从家经逐个地点达到目的地的最佳路径。 2、实验材料： 软件：ArcGIS Desktop 9.x ， 实验数据：文件夹ex6中，一个GeoDatabase地理数据库：City.mdb，内含有城市交通网、超市分布图，家庭住址以及网络关系。 三、实验内容及步骤 首先启动ArcMap，选择ex6\city.mdb，再双击后选择将整个要素数据集“city”加载进来，然后将“place”点状要素以“HOME”字段属性值进行符号化，1值是家，0值是超市。 第1步无权重最佳路径的选择 加载“设施网络分析”工具条（“视图”>>“工具条”，勾选“设施网络分析”），点选旗标和障碍工具板下拉箭头，将旗标放在家和想要去的超市点上。
第2步加权最佳路径选择 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标放在家和想去的某个超市点上。 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则以长度为 比重为基础的最短路径将显示出来，这条路径的总成本将显示在状态列。
最短路径问题的算法分析及建模案例
最短路径问题的算法分析及建模案例 一.摘要 (3) 二.网络最短路径问题的基础知识 (5) 2.1有向图 (7) 2.2连通性................... 错误！未定义书签。 2.3割集....................... 错误！未定义书签。 2.4最短路问题 (8) 三．最短路径的算法研究.. 错误！未定义书签。 3.1最短路问题的提出 (9) 3.2 Bellman最短路方程错误！未定义书签。 3.3 Bellman-Ford算法的基本思想错误！未定义书签 3.4 Bellman-Ford算法的步骤错误！未定义书签。 3.5实例....................... 错误！未定义书签。 3.6 Bellman-FORD算法的建模应用举例错误！未定义 3.7 Dijkstra算法的基本思想 (9) 3.8 Dijkstra算法的理论依据 (9) 3.9 Dijkstra算法的计算步骤 (9) 3.10 Dijstre算法的建模应用举例 (10) 3.11 两种算法的分析错误！未定义书签。
1.Diklstra算法和Bellman-Ford算法 思想有很大的区别错误！未定义书签。 Bellman-Ford算法在求解过程中，每 次循环都要修改所有顶点的权值，也就 是说源点到各顶点最短路径长度一直 要到Bellman-Ford算法结束才确定下 来。...................... 错误！未定义书签。 2.Diklstra算法和Bellman-Ford算法 的限制.................. 错误！未定义书签。 3.Bellman-Ford算法的另外一种理解错误！未定 4.Bellman-Ford算法的改进错误！未定义书签。 摘要 近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径 问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等 诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的 一个典型例子。 由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究， 使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最 短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题
GIS应用技能训练 基于多因素与层次模型的校 题目 园火灾救援最佳路径分析 学院资源与环境工程学院 专业地理信息系统 班级1102班 姓名江瑶 指导教师黎华、胡杏花 2013 年7 月12 日
目录 摘要 (1) 1 背景以及分析的意义 (1) 2 训练要求 (1) 3 设计分析 (2) 3.1整体思路 (2) 3.2最佳路径的道路层次模型 (2) 3.2.1建立层次模型 (2) 3.2.2确定权系数 (3) 3.2.3实际调查 (4) 4 软件应用 (5) 4.1本次实验的道路数据获取 (5) 4.2对校园内外部矢量化并制图 (7) 4.3给校园各道路命名并且赋权值 (9) 4.4对校园内外道路进行拓扑构网 (9) 4.5对拓扑网进行最短和最佳路径分析 (11) 5 结果分析及评价 (11) 5.1校外最短路径结果及分析 (11) 5.2校内最短路径结果及分析 (11) 6 心得体会 (12) 致谢 (13) 参考文献 (13) 附录1 权值计算代码 (15) 附录2 所有道路权值 (15)
基于多因素与层次模型的校园火灾救援 最佳路径分析 摘要：最佳路径的求取实则是一个多目标综合决策问题。以往一些研究没有能全面分析问题，只注重与某个因素下的最佳路径，这使得分析结果不尽如人意，不能得到最佳结果。有些则综合了多种影响因素，然而在确定评价指标的权重时常采用专家评估的方法，这具有很大的随意性和主观性，有时会偏离客观实际，易于造成评价失准，致使结论缺乏真实性。 本文所提模型是综合了多目标决策与层次分析法的基于多因素影响与综合评判的最佳路径分析模型。模型在全面问题分析基础上先给出了影响最佳路径分析的几个重要影响因子，并利用层次分析法的思想构建了道路层次模型，确定了各影响因素的权系数。在综合评判时应用多目标决策模型与所提因素评分模型确定了各影响因素对路段的评分矩阵，并综合所求各因素的权系数得到最终路段的综合权值。最后以路段综合权值为路段属性进行Dijkstra算法求解，得到最佳路径。文中采用层次分析法来确定权值，将定性与定量分析相结合，利用严密的数学理论，去除随意性与主观性，表达了符合客观实际的因素影响权值，并且依据判断矩阵的一致性来检验权值的合理性，从而使得分析结论更准确、可靠。此次分析是当武汉理工大学某处发生火灾，分析消防车怎样最快到达火灾处。在学校外进行消防车到达校门口进行最短路径分析，对校内进行最佳路径分析。 关键词：多因素层次分析最佳路径校园 1 背景以及分析的意义 在当今大学校园中蕴藏着很多不确定因素有可能引发的灾害会危机师生生命财产安全，而为了防范并尽量减少这些灾害造成的影响，我们小组选定大学校园火灾快速救灾最佳路线决策作为此次超图软件实习主题，随之我们小组经详细讨论和合理分析最终确定使用“基于多因素决策与层次分析法的最佳路径模型”来计算火灾发生地周边各路径权值并利用SuperMap软件最佳路径自动分析来为消防车火灾扑救路线选择及火灾发生区域人员疏散路线选择做最佳路径决策分析。 2 训练要求 应用所学的地理信息系统原理与应用、地图学以及数字测图原理与方法中所学到的基
ArcEngine 最短路径分析 using System; using ESRI.ArcGIS.Carto; using ESRI.ArcGIS.Geometry; using ESRI.ArcGIS.Geodatabase; using https://www.doczj.com/doc/7e10774528.html,workAnalysis; namespace GisEditor { ///
实验十、网络分析（道路网络分析） 一、实验目的 网络分析是GIS空间分析的重要功能分。有两类网络，一为道路（交通）网络，一为实体网络（比如，河流、排水管道、电力网络）。此实验主要涉及道路网络分析，主要内容包括： ●最佳路径分析，如：找出两地通达的最佳路径。 ●最近服务设施分析，如：引导最近的救护车到事故地点。 ●服务区域分析，如：确定公共设施（医院）的服务区域。 通过对本实习的学习，应达到以下几个目的： (1)加深对网络分析基本原理、方法的认识； (2)熟练掌握ARCGIS下进行道路网络分析的技术方法。 (3)结合实际、掌握利用网络分析方法解决地学空间分析问题的能力。 二、实验准备 软件准备：ArcMap, 要求有网络分析扩展模块的许可授权 数据准备： Shape文件创建网络数据集（高速公路：Highways, 主要街道：Major Streets, 公园：Parks，湖泊：Lakes，街道：Streets） Geodatabase网络数据集：NetworkAnalysis.mdb：包含：街道图层：Streets 仓库图层：Warehouses 商店图层：Stores 在ArcMap中加载启用NetWork Anylyst网络分析模块： 执行菜单命令［工具Tools］>>[Extensions], 在［Extensions］对话框中点击[Network Analyst] 启用网络分析模块，即装入Network Analyst空间分析扩展模块。 道路网络分析步骤 1. 创建分析图层 2. 添加网络位置 3. 设置分析选项 4. 执行分析过程显示分析结果 三、实验内容及步骤 (一) 最佳路径分析 根据给定的停靠点，查找最佳路径（最省时的线路）
AE开发之基于几何网络的最短路径分析 1、实习目的 本次实习目的在于熟练掌握ArcGIS Engine开发工具并能够通过C#语言在VS2010开发环境中完成查询几何网络的最短路径分析的功能。 2、实习时间 2015年5月23日星期六 3、实习内容 3.1实验环境 操作系统：Win dows 2007 二次开发平台：VS 2010开发环境、ArcGIS Desktop10.0、AE开发组件3.2实验任务 完成基于几何网络分析的最短路径查询功能，即实现通过在几何网络地图中指定起始点，能够查询经过起始点的最短路线，并能够通过缩放功能在地图窗口居中显示。
3.3实验步骤 331新建项目 选择文件新建项目，如图选择项目类型中Visual C#，再选择Win dows Application ，记为“ FindShortPath ”，点击确定。 Vi-5.u-ai Bask Vtsual C? 丄VTiual C# Wnd OWE Wet WPF.ES8?VtsuaJ C# 思于宙ata育wirdow琵体泗户畀酝 应用程序的：E目 v^ ual a ArcGJS Cloud ReporiEjng SharePoint Silwirliglhr WCF VkiuJ C# VrtualC# Fi ndShortP firth] ffiHCL）：d:\doicurnervt或yi翼Idl studig 201D\Pr-pjcct5■ 翩WE3S3T 绘兴方宝宕粗⑷：FindShortPisth Window敷迪用邕了 WPF窗览H应用呈 甲 WindoMrs 觀男 WPF用户邮注 Workflow WPF自走:込陛 ft黑 Vkud C# *曲^方妄缠目云口 "⑹???
最短路问题及其应用 1 引言 图论是应用数学地一个分支，它地概念和结果来源非常广泛，最早起源于一些数学游戏地难题研究，如欧拉所解决地哥尼斯堡七桥问题，以及在民间广泛流传地一些游戏难题，如迷宫问题、博弈问题、棋盘上马地行走路线问题等．这些古老地难题，当时吸引了很多学者地注意．在这些问题研究地基础上又继续提出了著名地四色猜想和汉米尔顿（环游世界）数学难题． 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学地发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域地问题时，发挥出越来越大地作用．在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题地有力工具之一. 最短路问题是图论理论地一个经典问题.寻找最短路径就是在指定网络中两结点间找一条距离最小地路.最短路不仅仅指一般地理意义上地距离最短,还可以引申到其它地度量,如时间、费用、线路容量等. 最短路径算法地选择与实现是通道路线设计地基础,最短路径算法是计算机科学与地理信息科学等领域地研究热点,很多网络相关问题均可纳入最短路径问题地范畴之中.经典地图论与不断发展完善地计算机数据结构及算法地有效结合使得新地最短路径算法不断涌现. 2 最短路 2.1 最短路地定义 对最短路问题地研究早在上个世纪60年代以前就卓有成效了,其中对赋权图()0 w≥地有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出地, ij 该算法能够解决两指定点间地最短路,也可以求解图G中一特定点到其它各顶点地最短路.后来海斯在Dijkstra算法地基础之上提出了海斯算法.但这两种算法都不能解决含有负权地图地最短路问题.因此由Ford提出了Ford算法,它能有效地解决含有负权地最短路问题.但在现实生活中,我们所遇到地问题大都不含负权,所以我们在()0 w≥地情况下选择Dijkstra算法. ij 定义①1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e地权,则称这
C源码ArcEngine最短路径分析ArcEngine 最短路径分析(源码)几何网络 using System; using ESRI.ArcGIS.Carto; using ESRI.ArcGIS.Geometry; using ESRI.ArcGIS.Geodatabase; using https://www.doczj.com/doc/7e10774528.html,workAnalysis; namespace GisEditor { ///
public IMap SetOrGetMap { set{ m_ipMap = value;} get{return m_ipMap;} } //打开几何数据集的网络工作空间 public void OpenFeatureDatasetNetwork(IFeatureDataset FeatureDa taset) { CloseWorkspace(); if (!InitializeNetworkAndMap(FeatureDataset)) Console.WriteLine( "打开network出错"); } //输入点的集合 public IPointCollection StopPoints { set{m_ipPoints= value;} get{return m_ipPoints;} } //路径成本 public double PathCost { get {return m_dblPathCost;} }
最短路径问题的算法分析及建模案例 一.摘要 (2) 二.网络最短路径问题的基础知识 (3) 2.1有向图 (5) 2.2连通性.............................................................................................. 错误！未定义书签。 2.3割集.................................................................................................. 错误！未定义书签。 2.4最短路问题 (6) 三．最短路径的算法研究............................................................................. 错误！未定义书签。 3.1最短路问题的提出 (6) 3.2 Bellman最短路方程...................................................................... 错误！未定义书签。 3.3 Bellman-Ford算法的基本思想.................................................... 错误！未定义书签。 3.4 Bellman-Ford算法的步骤............................................................ 错误！未定义书签。 3.5实例.................................................................................................. 错误！未定义书签。 3.6 Bellman-FORD算法的建模应用举例............................................ 错误！未定义书签。 3.7 Dijkstra算法的基本思想 (6) 3.8 Dijkstra算法的理论依据 (6) 3.9 Dijkstra算法的计算步骤 (6) 3.10 Dijstre算法的建模应用举例 (7) 3.11 两种算法的分析........................................................................... 错误！未定义书签。 1.Diklstra算法和Bellman-Ford算法思想有很大的区别 ...... 错误！未定义书签。 Bellman-Ford算法在求解过程中，每次循环都要修改所有顶点的权值，也就是说 源点到各顶点最短路径长度一直要到Bellman-Ford算法结束才确定下来。错误！未定义书签。 2.Diklstra算法和Bellman-Ford算法的限制.......................... 错误！未定义书签。 3.Bellman-Ford算法的另外一种理解........................................ 错误！未定义书签。 4.Bellman-Ford算法的改进........................................................ 错误！未定义书签。