基于最短线路游览重庆主城区的Dijkstra算法应用

1、重庆邮电大学研究生堂下考试答卷 2012学年第一学期考试科目 图论及其算法 姓 名 张 磊 年 级 研一（1）班 专 业 计算机技术 2012年 12 月 15 日基于最短线路游览重庆主城区的Dijkstra算法应用专业：计算机技术 学号：S120231048 姓名：张磊摘要：重庆，有“山城”之名，又有“江都”之称。重庆众多的旅游景点自然也就让人目不暇接，然而，遇到一个问题，那就是如何让自己在有限的旅行时间内用最短的路径来游览重庆最多的景点。通过图论课程的学习，可以发现利用图论中的最短路径算法可以很好地解决这一旅行问题。本文运用了图论中的最短路径算法，以重庆市辖区内的旅游景点为背景，选取了几个

2、典型的景点为模拟对象，通过Dijkstra算法获得从重邮出发到某一景点之间的最短路径并通过Java语言编程实现，以方便旅行者选择合适的旅行线路。关键字：最短路径，Dijkstra算法，旅游线路1、概述俗话说，“上有天堂，下有苏杭，还有重庆的灯火辉煌”，重庆除了美丽的山城夜景外，市辖区内还有数不胜数的著名旅游景点，如磁器口、解放碑、大礼堂等。然而，对于仅限于在五一或十一这样的节假日来重庆游玩的人来说，如何在自己有限的旅行时间里用最短的路径最经济的花费来游览重庆最多的景区，事先制定合适的旅行计划显得尤为的重要。而图论中的最短路径分析方法及其算法广泛应用在我们的工作生活中，上述旅行问题便是很好的一个

3、应用性的实例。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法的具体形式包括多种，如确定起点的最短路径问题、确定终点的最短路径问题、确定起点终点的最短路径问题、全局最短路径问题等。而确定起点的最短路径问题就是已知起始节点，求最短路径的问题，其用于解决最短路径问题的算法被称作“最短路径算法”。本文中假若旅行者住在重邮，要获取重邮到各个旅游景点的最短路径，适合使用Dijkstra算法。2、Dijkstra算法描述迪科斯彻算法(Dijkstras algorithm)是由荷兰计算机科学家艾兹赫尔戴克斯特拉发明的。算法解决的是有向图中单个源点到其

4、他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。该算法的输入包含了一个有权重的有向图G，我们用V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们用E表示所有边的集合，而边的权重则由权重函数 w：E 0, 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离，任两点间路径的权重，就是该路径上所有边的权重总和。已知有V中有顶点 s 及 t，Dijkstra算法可以找

5、到 s 到 t 的最低权重路径(例如最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶

6、点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。Dijkstra算法具体步骤：（1）初始时，S只包含源点，即Sv的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边或u不是v的出边邻接点）。（2）从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所有顶点都

7、包含在S中。3、Dijkstra算法用于解决旅行线路问题的建模实现本文主要以市辖区内的主要景点为模型，选取了六处典型的景点分别是：重邮、解放碑、洋人街、朝天门、磁器口、大礼堂。景点之间的路径用直线相连接，直线上的数字表示两景点之间的距离（单位为公里），如下图所示：将这六个景点分别看做是图的六个定点并对其进行编号：V0V5，考察由重邮到各个景点之间的最短路径就转化成了求图G的顶点V0到其余各个顶点的最短路径，边上的数字代表该条路径上的权值。4、采用Dijkstra算法的旅行问题编程实现为求从重邮出发到各个景点的最短路径问题，也就是求图G中V0到其余各个顶点的最短路径，本文以求重邮到磁器口的最短路

8、径，也即V0到V5的最短路径为例，采用Java语言实现的具体方法如下：第一步：根据图来建立权值矩阵：int W = 0, 8, 14, -1, -1, -1 , 8, 0, 18, 5, 26, -1 , 14, 18, 0, -1, 12, -1 , -1, 5, -1, 0, 13, 17 , -1, 26, 12, 13, 0, 24 , -1, -1, -1, 17, 24, 0 ； (-1表示两边不相邻,权值无限大)例如：W02=14 表示点V0到点V2的权值为14W03= -1表示点V0与V3不相邻，所以权值无限大。第二步：对V0标号；V0到其它点的路径得到 distance： 0

9、,8,14,-1,-1,-1；找到V0到各点中权值最小的那个点（标号的点除外,-1代表无限大），故得到8即对应的下标1，得到V1；对V1标号，然后更改V0通过V1到其它点的路径得到 distance： 0, 8, 26, 34, 13, -1；第三步：找到distance中权值最小的那个点（标号的点除外）得到V3，对V3标号，然后更改V0通过V1-V3到其它点的路径得到 distance： 0, 8, 26, 34, 13, -1；第四步：找到distance中权值最小的那个点（标号的点除外）得到V4,对V4标号，然后更改V0通过V1-V3到其它点的路径得到 distance： 0, 8, 3

10、, 26, 34, 26； 最后只剩下V5没有被标号，就找到V5了。结束！源代码如下：1 package com.xh.Dijkstra; 2 3 /该Java程序用来求得一个图G的最短路径矩阵 4 public class ShortestDistance_V4 5 public static int dijkstra(int W1, int start, int end) 6 boolean isLabel = new booleanW10.length;/ 是否标号 7 int min = Integer.MAX_VALUE; 8 int indexs = new intW10.leng

11、th;/ 所有标号的点的下标集合 9 int i_count = -1; 10 int index = start;/ 从初始点开始 11 int presentShortest = 0; 12 int distance = W1start.clone();/ v0到各点的最短距离的初始值 13 indexs+i_count = index;/ 把已经标号的下标存入下标集中 14 isLabelindex = true; 15 while (true) 16 / 第一步：标号v0,即w00找到距离v0最近的点 17 18 min = Integer.MAX_VALUE; 19 for (int

12、 i = 0; i distance.length; i+) 20 if (!isLabeli & distancei != -1 & i != index) 21 / 如果到这个点有边,并且没有被标号 22 if (distancei distanceindex) 35 presentShortest = distanceindex; 36 else 37 presentShortest += W1indexsi_count - 1index; 38 39 40 / 第二步：奖distance中的距离加入vi 41 for (int i = 0; i distance.length; i+)

13、 42 / 如果vi到那个点有边，则v0到后面点的距离加 43 if (distancei = -1 & W1indexi != -1) / 如果以前不 可达，则现在可达了 44 distancei = presentShortest + W1indexi; 45 else if (W1indexi != -1 46 & presentShortest + W1indexi distancei) 47 distancei = presentShortest + W1indexi; 48 49 50 51 52 return distanceend - distancestart; 53 54

14、55 public static int getShortestPathMatrix(int W) 56 int SPM = new intW.lengthW.length; 57 /多次利用dijkstra算法 58 for (int i = 0; i W.length; i+) 59 for (int j = i + 1; j W.length; j+) 60 SPMij =dijkstra(W, i, j); 61 SPMji = SPMij; 62 63 64 return SPM; 65 66 67 public static void main(String args) 68 /*

15、 顶点集：V=v1,v2,，vn */ 69 int W = 0, 8, 13, 14 , 8, 0, 26, -1 , 13, 17, 0, 26 , 70 14, -1, 26, 0 ; 71 int W1 = 0, 8, 14, -1, -1, -1 , 8, 0, 18, 5, 26, -1 ,72 14, 18, 0, -1, 12, -1 , -1, 5, -1, 0, 13, 17 , 73 -1, 26, 12, 13, 0, 24 , -1, -1, -1,17, 24, 0 ; 74 / 建立一个权值矩阵 75 int D = getShortestPathMatrix(W

16、1); 76 /输出最后的结果 77 for (int i = 0; i D.length; i+) 78 for (int j = 0; j Di.length; j+) 79 System.out.print(Dij + ); 80 81 System.out.println(); 82 83 84 5、总结最短路径算法中的Dijkstra算法很好的解决了旅行中确定起点的最短路径问题，在我们的日常生活中得到了广泛的应用。基于Dijkstra算法的改进算法有很多种，在一定程度上优化了最短路径的计算过程，并有效的降低了算法的时间复杂度，希望通过图论知识学习的深入和使用编程语言实现算法的基础之上，用图论中学到知识来真正的解决在工程中的实践问题。6、参考文献1殷剑宏,吴开亚著.图论及其算法.中国科学技术大学出版社.2005/032王桂平,王衍著.图论算法理论、实现及应