最短路径算法分类与应用研究

1、课题结题论文题 目 最短路径算法分类与应用研究 学 院 专 业 班 级 学生姓名 指导教师 2008年10月最短路径算法分类与应用研究姓 名: 班 级:指导教师:摘要本文研究目的在于收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。通过应用最短路径算法中的蚁群算法来解决浙江旅行商问题，以各城市经纬度作为初始条件，通过MATLAB程序计算最短路径，并画出最短路线图。关键词最短路径算法，最短路径应

2、用，蚁群算法，浙江旅行商目 录摘要I关键词I第一章绪论2第二章最短路径算法2一、Dijkstra算法21、适用条件和范围22、算法描述23、算法实现2二、A*算法21、适用条件和范围32、算法原理33、算法描述3三、Bellman-Ford算法31、适用条件和范围32、算法描述43、算法实现4四、Topological Sort(拓扑排序)算法41、适用条件和范围42、算法描述43、算法实现4五、SSSP On DAG算法41、适用条件和范围42、算法描述53、算法实现5六、Floyd算法51、适用范围52、算法描述53、算法小结5七、Prim算法51、适用范围5

3、2、算法描述53、算法实现5八、Kruskal算法61、适用范围62、算法描述63、算法实现6九、Johnson算法61、适用范围62、算法实现6第三章最短路径算法应用6一、TSP问题的介绍6二、TSP问题算法的介绍61、贪心算法62、模拟退火算法73、遗传序列算法74、蚁群算法8三、算法应用81、解决浙江旅行商问题时算法描述82、蚁群算法的MATLAB程序描述93、蚁群算法解决浙江旅行商问题11第四章总结12致谢12参考文献13第一章 绪论随着计算机科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正因为最短路径问题在实际生产

4、生活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题即已知起始结点，求最短路径的问题；确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题；在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题；确定起点终点的最短路径问题即已知起点和终点，求两结点之间的最短路径；全局最短路径问题求图中所有的最短路径。用于解决最短路径问题的算法被称作最短路径算法。本文研究目的在于收集整

5、理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。第二章 最短路径算法本课题旨在总结归纳最短路径的普遍算法，经收集资料发现最短路径算法主要有：Dijkstra算法、A*算法 、Bellman-Ford算法、Topological Sort(拓扑排序)算法、SSSP On DAG算法、Floyd算法 、Prim算法、Kruskal算法及Johnson算法。其中最常用的路径

6、算法有：Dijkstra算法、A*算法、Bellman-Ford算法及Floyd算法。一、Dijkstra算法1、适用条件和范围：（1）单源最短路径（从源点s到其它所有顶点v）；（2）有向图和无向图（无向图可以看作，同属于边集E的有向图）；（3）所有边权非负（任取都有）。2、算法描述：如果 v1 v2 v3 v4 是 v1 v4 的最短路径，则 v1 v2 v3 一定是 v1 v3 的最短路径。 v2 v3 v4 一定是 v2 v4 的最短路径。3、算法实现：（1）初始化：disv=maxint ；diss=0；pres=s;S=s；（2）For i:=1 to 

7、n取V-S中的一顶点u使得disu=mindisv|vV-SS=S+uFor V-S中每个顶点v do Relax （3）算法结束：disi为s到i的最短距离；prei为i的前驱节点。程序见参考文献8。二、A*算法1、适用条件和范围：A*算法属于一种启发式搜索。它扩展结点的次序类似于广度优先搜索，但不同的是每生成一个子结点需要计算估价函数F，以估算起始结点到该结点的代价及它到达目标结点的代价的和；每当扩展结点时，总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象，以便使搜索尽量沿最有希望的方向进行。因此，A*算法只要求产生问题的全部状态空间的部分结点，就可以

8、求解问题了，搜索效率较高。确定估价函数方法通常是：搜索到该结点的深度+ 距离目标最近的程度。2、算法原理：如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）状态空间图搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。3、算法描述：（1）初始状态： OPEN=A5;CLOSED=;（2）估算A5，取得搜有子节点，并放入OPEN表中；OPEN=B4, C4, D6; CLOSED=A5（3）估算B4，

9、取得搜有子节点，并放入OPEN表中；OPEN=C4, E5, F5, D6; CLOSED=B4, A5（4）估算C4；取得搜有子节点，并放入OPEN表中；OPEN=H3, G4, E5, F5, D6;CLOSED=C4, B4, A5（5）估算H3，取得搜有子节点，并放入OPEN表中；OPEN=O2, P3, G4, E5, F5, D6; CLOSED=H3C4, B4, A5（6）估算O2，取得搜有子节点，并放入OPEN表中；OPEN=P3, G4, E5, F5, D6; CLOSED=O2, H3, C4, B4, A5（7）估算P3，已得到解。三、Bellman-Ford算法1、

10、适用条件和范围：（1）单源最短路径(从源点s到其它所有顶点v)；（2）有向图和无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)；（3）边权可正可负(如有负权回路输出错误提示)；（4）差分约束系统。2、算法描述：（1）对每条边进行|V|次Relax操作；（2）如果存在（u,v）E使得disu+w<disv，则存在负权回路；否则disv即为s到v的最短距离，prev为前驱。3、算法实现：（1）PASCA语言 For i:=1 to |V|-1 do For 每条边(u,v)E do Relax(u,v,w); For每条边(u,v)E do If disu+w<dis

11、v Then Exit(False)（2）C/C+语言 void bellman_ford(int v) for 1 to n initialize distv; for 2 to n-1 (i) for 1 to n (j) for 1 to n (k) if edgekj > 0 && distk > edgekj+distj 更新当前值 四、Topological Sort(拓扑排序)算法1、适用条件和范围：（1）AOV网(Activity On Vertex Network)；（2）有向图；（3）作为某些算法的预处理过

12、程(如DP)。2、算法描述：（1）每次挑选入度为0的顶点输出(不计次序)；（2）如果最后发现输出的顶点数小于|V|，则表明有回路存在。3、算法实现：（1）数据结构：adj:邻接表;有4个域u,v,w,next；indgri:顶点i的入度；stack:栈；（2）初始化:top=0 (栈顶指针)；（3）将初始状态所有入度为0的顶点压栈；（4）I=0 (计数器)；（5）While栈非空(top>0) do顶点v出栈；输出v；计数器增1；For与v邻接的顶点u doa. dec(indgru)；b. If indgru=0&#

13、160;then顶点u入栈；（6）EXIT(I=|V|)。五、SSSP On DAG算法1、适用条件和范围：（1）DAG(Directed Acyclic Graph,有向无环图)；（2）边权可正可负。2、算法描述：（1）Toposort；（2）If Toposort=False Then HALT(Not a DAG)；（3）For拓扑序的每个顶点u doFor u的每个邻接点v doRelax(u,v,w)；（4）算法结束后：如有环则输出错误信息；否则disi为s到i的最

14、短距离，prei为前驱顶点。3、算法实现：此算法时间复杂度O(V+E)，时间和编程复杂度低，如遇到符合条件的题目(DAG)，推荐使用。还有，此算法的步骤（3）可以在toposort中实现，这样即减小了此算法复杂度的一个系数。六、Floyd算法1、适用范围：  （1）APSP(All Pairs Shortest Paths)；（2）稠密图效果最佳；（3）边权可正可负。2、算法描述：（1）初始化：disu,v=wu,v。（2）For k=1 to nFor i=1 to nFor j=1

15、 to nIf disi,j>disi,k+disk,j ThenDisi,j=disi,k+disk,j。（3）算法结束：dis即为所有点对的最短路径矩阵。3、算法小结：此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。4、算法实现：见参考文献11。七、Prim算法1、适用范围：（1）用于求无向图的最小生成树；（2）无向图(有向图的是最小树形图)；（3）多用于稠密图。2、算法描述：设图G =（V，E），其生成树的顶点集合为U。（1）把v0放入U；（2）在所有uU，vV-U的边(u，v)E中找一条最小权值

16、的边，加入生成树；（3）把（2）找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行（2）。3、算法实现：（1）集合：设置一个数组set(i=0,1,.,n-1)，初始值为0，代表对应顶点不在集合中（注意：顶点号与下标号差1)；（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替；（3）具体程序见参考文献12。八、Kruskal算法1、适用范围：（1）MST(Minimum Spanning Tree,最小生成树)；（2）无向图(有向图的是最小树形图)；（3）多用于稀疏图；（4）边已经按权值排好序给出。2、算法描述：（1）将边按非降序排列

17、；（2）While合并次数少于|V|-1取一条边(u,v)(因为已经排序，所以必为最小)If u,v不属于同一连通分量thena.合并u,v所在的连通分量b.输出边(u,v)c.合并次数增1；tot=tot+W(u,v)（3）算法结束：tot为MST的总权值。3、算法实现：见参考文献13。九、Johnson算法1、适用范围：Johnson算法适用于求All Pairs Shortest Path。2、算法实现：Johnson算法应用了重标号技术（1）先进行一次Bellman-Ford算法；（2）然后对原图进行重标号，w'(i,j)=hi-hj+w(i,j)；（3）然后对每个点

18、进行一次Dijkstra。第三章 最短路径算法应用一、TSP问题的介绍TSP问题，即旅行商问题，是一种典型的组合最优化问题，可描述为某旅行商欲往n个城市推销货物，从某个城市出发，沿途经过各个城市一次后返回出发城市，要确定一条行走的路线，计算途径n个城市的最短距离，即给定个城市和两两城市之间的距离，确定一条经过每个城市并且仅经过一次的路线，要求总路径最短。TSP分为2类，即对称TSP和不对称TSP。对于城市数目为n的地图, 共有n种不同的路径。城市越多,可能的路径也越多。而且路径的增加速度非常快且是非线形的。当n很大时，去尝试每一种可能的路径是不可能的，所以需要设计一个有效的算法去寻找最短的路径

19、。二、TSP问题算法的介绍1、贪心算法贪心算法的主要思想是永远选择当前最短的路径。这是解决TSP问题的最简便的算法。贪心算法容易实现但是效率不好。如下图所示:有4个城市:A，B，C和D。距离从A到B是5公里，A到C是6公里，A到D是9公里，B到C是3公里, B到D是7公里，C到D是8公里。假设我们一开始在A，比较A到其他点的路径长度，找出A到B是最短的路径(5公里)。我们从A到B，然后设定A和B之间的距离无限大。在B我们找出B到C(3公里)是最短的路径。如此然后去C，再到D。所以，此算法则总是选择最短的路径。2、模拟退火算法模拟退火算法是一种求解大规模组合优化问题的方法，对于NP-完全组合优化

20、问题尤其有效。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓慢降温(即退火)，使之达到能量最低点。反之，如果急速降温(即淬火)则不能达到最低点。加温时, 固体内部粒子随温升变为无序状，内能增大，而缓慢降温时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(- E/(kT), 其中E为温度T时的内能，E为其改变量，k为Boltzman常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法: 由初始解i和控制参数初值t开始，对

21、当前解重复产生“新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值, 算法终止时的当前解即为所得近似最优解。所以我们可以通过上面的思想写出解决TSP问题的模拟退火算法。步骤如下:（1）初始化: 初始温度T(充分大), 初始解状态s(随机选取一条TSP路线, 算出走完此路线的长度Cost(s)作为评价函数, 这是算法迭代的起点), 每个T值的迭代次数L；（2）对k=1至k=L做第(3)至第(6)步；（3）产生新解 ( 一般利用2-opt算法来产生新的路径)；（4）计算增量Cost=Cost()- Cost(s)，其中Cost(s)为评价函数；（5）若则接受作为新的当前解, 否则以概率exp(-

22、/T)接受作为新当前解；（6）如果满足终止条件则输出当前解作为最优解, 结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法；（7）T逐渐减少，且T趋于0，然后转第2步运算。3、遗传序列算法遗传算法简称GA(Genetic Algorithm), 在本质上是一种不依赖具体问题的直接搜索方法。遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“ 染色体”， 也即是假设解。然后, 把这些假设解置于问题的“ 环境”中, 并按适者生存的原则，从中选择出较适应环境的“ 染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“ 染色体

23、”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“ 染色体”上，它就是问题的最优解。步骤如下:（1) 产生一群染色体(不同的游历路径) 然后计算评估每个染色体的健壮度(总路径长度)。（2) 选留健壮度较好的染色体(总路径较短的路径)，剩下的作为父染色体；（3) 父染色体交换, 倒转或移位产生下一代染色体(其中有5%的染色体变异的概率)；（4) 在下一代染色体的基础上回到第（1）步骤；（5) 循环整个程序多次，记录下每代的最好的染色体；（6) 选择其中最优秀的染色体作为最优解。4、蚁群算法首先引入TSP中常用符号：m为蚁群中蚂蚁数量；为时刻位于城市的蚂蚁个数，且；为城市i和j之间的距离

24、；为边（i,j）的能见度，反映由城市i转移到城市j的启发程度；为边（i,j）上的信息素轨迹强度；为蚂蚁在边（i,j）上留下的单位长度轨迹信息素量；为蚂蚁k的转移概率；j是尚未访问的城市。在初始时刻，各条路径上的信息素量相等，设，（为常数），蚂蚁被随机放到某个城市，然后根据各条路径上的信息素量选择下一个城市。在时刻， （1）式中：表示蚂蚁下一步允许选择的城市；和为2个参数，分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。为了阻止蚂蚁重复访问，为每只蚂蚁都设计一个被称为禁忌表（tabu list）的数据结构。经过 个时刻，蚂蚁完成一次循环，各路径上信息素“蒸发”和增加的

25、量根据下式调整： （2）式中：表示信息素蒸发后的剩余，则（1-）为衰减系数，表示信息素的减少；表示信息素增加的量，在式（1）中 （3）表示第k只蚂蚁在时刻留在路径上的信息素量；，Q为常数，为第k个蚂蚁爬过路径的长度，等于的值。至此，一个蚂蚁的循环过程结束，由此反复迭代多次，最终得出优化结果。三、算法应用1、解决浙江旅行商问题时算法描述 第一步：初始化，将所有城市坐标列出，并计算出两两城市之间的距离。 第二步：用蚁群算法迭代一次，得出一个最优解，由此来计算出和的大小。由得到信息素的初值，然后进行信息素更新，判断是否超出范围，如果超出，则限制大小。第三步：继续迭代，直到第三次，得到。判断信息素是否

26、超出，如果超出，则限制大小。第四步：往复迭代计算，直到达到最大迭代次数。每一次计算都得出新的最优解，所以每一次计算中，和都会重新被更新，是一个动态变化范围。 第五步：输出最后结果。2、蚁群算法的MATLAB程序描述2.1 蚁群算法解决TSP的主要符号说明：n 为城市个数；C 为n个城市的坐标，n×2的矩阵；m 为蚁群中蚂蚁数量；NC_max 最大迭代次数；Alpha 表征信息素重要程度的参数；Beta 表征启发式因子重要程度的参数；Rho 信息素蒸发系数；Q 信息素增加强度系数；R_best 各代最佳路线；L_best 各代最佳路线的长度；2.2 MATLAB程序描述：第一步 变量初

27、始化n=size(C,1); D=zeros(n,n); for i=1:nfor j=1:nif i=jD(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2)0.5;elseD(i,j)=eps;endD(j,i)=D(i,j);endendEta=1./D; Tau=ones(n,n); Tabu=zeros(m,n); NC=1; R_best=zeros(NC_max,n); L_best=inf.*ones(NC_max,1); L_ave=zeros(NC_max,1); while NC<=NC_max 第二步 将m只蚂蚁放到n个城市上Randpos

28、=;for i=1:(ceil(m/n)Randpos=Randpos,randperm(n);endTabu(:,1)=(Randpos(1,1:m)'第三步 m只蚂蚁选择下一座城市，完成各自的周游for j=2:nfor i=1:mvisited=Tabu(i,1:(j-1); J=zeros(1,(n-j+1); P=J; Jc=1;for k=1:nif length(find(visited=k)=0J(Jc)=k;Jc=Jc+1;endendfor k=1:length(J)P(k)=(Tau(visited(end),J(k)Alpha)*(Eta(visited(end

29、),J(k)Beta);endP=P/(sum(P);Pcum=cumsum(P);Select=find(Pcum>=rand);to_visit=J(Select(1);Tabu(i,j)=to_visit;endendif NC>=2Tabu(1,:)=R_best(NC-1,:);End第四步 记录本次迭代最佳路线L=zeros(m,1);for i=1:mR=Tabu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);endL(i)=L(i)+D(R(1),R(n);endL_best(NC)=min(L);pos=find(L=L_be

30、st(NC);R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);NC=NC+1第五步 更新信息素Delta_Tau=zeros(n,n);for i=1:mfor j=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;Tabu=zeros(m,n);E

31、nd第六步 输出结果Pos=find(L_best=min(L_best);Shortest_Route=R_best(Pos(1),:)Shortest_Length=L_best(Pos(1)DrawRoute(C,Shortest_Route)function DrawRoute(C,R) N=length(R);scatter(C(:,1),C(:,2);hold onplot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)hold onfor ii=2:Nplot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii)

32、,2)hold onend3、蚁群算法解决浙江旅行商问题浙江旅行商问题初始参数设置如下： 蚁群中蚂蚁数量m=200；信息素重要程度的参数Alpha=1；启发式因子重要程度的参数Beta=5；信息素蒸发系数Rho=0.1；最大迭代次数NC_max=200；信息素增加强度系数Q=100。浙江省33个城市的坐标C（以33城市的经纬度作为城市的相对坐标），如下表：标号城市北纬东经标号城市北纬东经标号城市北纬东经1杭州30.16120.112兰溪29.12119.2823桐乡30.38120.322慈溪30.11121.1513临海28.51121.0824温岭28.22121.213东阳29.1612

33、0.1414丽水28.27119.5425温州28.01120.394奉化29.39121.2415龙泉28.04119.0826萧山30.09120.165富阳30.03119.5716宁波29.52121.3327义乌29.18120.046海宁30.32120.4217平湖30.42121.0128乐清28.08120.587湖州30.52120.0618衢州28.58118.5229余杭30.26120.188建德29.29119.1619瑞安27.48120.3830余姚30.02121.19江山28.45118.3720上虞30.01120.5231永康29.54120.0110嘉

34、兴30.46120.4521绍兴30120.3432舟山30.01122.0611金华29.07119.3922台州28.41121.2733诸暨29.43120.14运行蚁群算法，所得到的最短路线结果为：321641322242825191415918812112733331572912621206231017230即，舟山宁波奉化临海台州温岭乐清温州瑞安丽水龙泉江山衢州建德兰溪金华义乌东阳诸暨永康富阳湖州余杭杭州萧山绍兴上虞宁海桐乡嘉兴平湖慈溪余姚由于采用的是相对坐标，即城市的经纬度，因此不能算出具体最短路径是多长，如果采用实际地理坐标，则在运行后的MATLAB程序结果里可以看见所计算出的最短路径长度。浙江旅行商最短路线图如下图：第四章 总结通过收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题，由结果可以看出，蚁群算法运用于浙江旅行商问题，在结果上表现出令人满意的效果。在进一步的研究中，将继