最短路径分析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 exampleAbstract：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 city0 引言随着西部旅游业如火如荼的发展，天水市自驾旅游开始被越来越多的人选择。

自驾车旅游者追求以最少的花销走更远的路，看更优美的风景。

因此设计出一条多景点间距离最短（或费用，时间最少）的旅游线路是自驾车游客的现实需求[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：将判断矩阵每一列归一化 1ijn ki k b b b==∑ ()1,2,,i n =(1)Step2：对按列归一化的判断矩阵，再按行求和 1ni ij j W b ==∑ ()1,2,,i n =(2)Step3：将向量12(,,,)T i n W W W W =归一化：1ii 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 iAW 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 标号： ()jV 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 标号的最小值：()()00min V j j V TT = (6) 并将点v jo 的T 标号修改为P 标号，即令P(v jo )=0,然后再转入Step2。

3实例分析以天水市3A 级旅游景点为例，应用AHP 决策分析方法将旅游地选择问题模型化、数量化。

通过对各层次各因素之间的比较和计算，得出不同景点旅游价值的权重，从而为旅游地的选择提供依据，再结合Dijkstar 算法求出各旅游景点的最短路径。