《最短路径问题的算法分析及建模案例.pdf》由会员分享，可在线阅读，更多相关《最短路径问题的算法分析及建模案例.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-最短路径问题的算法分析及建模案例 一.摘要 1 二.网络最短路径问题的根底知识 2 2.1 有向图 3 2.2 连通性错误!未定义书签。2.3 割集错误!未定义书签。2.4 最短路问题 4 三最短路径的算法研究错误!未定义书签。3.1 最短路问题的提出 4 3.2 Bellman 最短路方程错误!未定义书签。3.3 Bellman-Ford 算法的根本思想错误!未定义书签。3.4 Bellman-Ford 算法的步骤错误!未定义书签。3.5 实例错误!未定义书签。3.6 Bellman-FORD 算法的建模应用举例错误!未定义书签。3.7 Dijkstra 算法的根本思想 5 3.8 Dij
2、kstra 算法的理论依据 5 3.9 Dijkstra 算法的计算步骤 5 3.10 Dijstre 算法的建模应用举例 6 3.11 两种算法的分析错误!未定义书签。1.Diklstra 算法和 Bellman-Ford 算法思想有很大的区别错误!未定义书签。Bellman-Ford 算法在求解过程中，每次循环都要修改所有顶点的权值，也就是说源点到各顶点最短路径长度一直要到 Bellman-Ford 算法完毕才确定下来。错误!未定义书签。2.Diklstra 算法和 Bellman-Ford 算法的限制错误!未定义书签。3.Bellman-Ford 算法的另外一种理解错误!未定义书签。4.
3、Bellman-Ford 算法的改良错误!未定义书签。摘要 近年来计算机开展迅猛，图论的研究也得到了很大程度的开展，而最短路径问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的一个典型例子。由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究，使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最短-路径问题的算法以及各算法之间的比拟，最后将这些算法再应用于实际问题的建模问题中。关键词：计算机 图论 交通道路网 最短路径 A.In this paper,puter developi
4、ng rapidly in recent years,graph theory research also have been greatly developed,and the shortest path problem is a typical problem in graph theory,it has been applied in geographical information science,puter science,and many other fields.And in the transportation network of the shortest route bet
5、ween two cities in is a typical e*ample of the shortest path problem.Due to the shortest path problem is widely used in various aspects,and the researchers on the in-depth study of the shortest path,make in the shortest path problem also generates a lot of classical algorithm.In this topic Ill sugge
6、st some algorithm and the algorithm of the shortest path problem between the parison,finally the algorithm is applied to the modeling of the actual problem again.Key words:puter graph traffic road network The shortest path 前言 最短路径问题是图论以及运筹学中的一个非常重要的问题，在生产实践，运输及工程建筑等方面有着十分广泛的应用。本文对图论中的最短路径问题进展分析，对其运算
7、解法进展分析寻求比拟快捷的模型解法；主要解决的是从*个顶点到其余各个顶点的最短路径问题。本文从 Floyd 算法以及 Dijkstra 算法两种算法入手，概述了这两种方法的原理，提出了求解最短路径问题的算法思想，并且对两种算法进展分析比拟，提出改良的方法。一 网络最短路径问题的根底知识 图 1 1.1 图 图 G 是一个无向图，其中有序二元组V,E，V=1v，2v,.nv是顶点集，E=ije是集，ije是一个无序二元组iv，jv它表示该边连接的是顶点iv，-jv。图 1 就是一个图。注释：图形的大小，位置，形状是无关紧要的。假设ije=iv,jv则称ije连接iv和jv；点iv和jv称为ije
8、的顶点，iv和jv是邻接的顶点；如果两条边有公共的一个顶点，则称这两边是邻接的。1.2 无环图 定义：没有环的图称之为无环图。1.3 简单图 定义：没有环且没有重边的图称之为简单图。设 G=V,E是一个简单图，则有|E|不大于|V|V|-1/2 1.4 完全图 定义：假设上式的等号成立则该图中每对顶点恰好有一条边相连，则称该图为完全图。1.5 有向图 定义：一个有向图 G 是一个有序二元组V,A，V=1v，2v，.,nv是顶点集，A=ija称为 G 的弧集，ija为有序二元组。称ija为iv连向jv的弧，ija为iv的出弧，jv的入弧；iv称为ija的得尾，jv称为 aij的头；iv称为jv的
9、前继，jv称为iv的后继。图 2 就是一个有向图。图 2 1.6 环 定义：头尾重合的弧称为环。1.7 简单有向图 定义：没有环和重弧的有向图称为简单有向图。-1.8 完全有向图 定义：设 G=V,E是一个简单有向图，则|A|不大于|V|V|-1，假设等号成立则称这样的图为完全有向图。1.9 途径，迹，路 定义：设图 G=V,E，假设它的*些顶点与边可以排成一个非空的有限交织序列0v，1e，1v,.ke,kv,这里该途径中边互不一样，则称为迹；如果顶点互不一样，则称之为路。显然路必为迹，但反之不一定成立。1.10 连通图 定义：图 G 中如果存在一条从顶点iv到jv的途径，则称iv和jv是连通
10、的。如果图 G 中任何两个顶点都是连通的，则称 G 是连通图。1.11 有向途径 定义：设有一个有向图 G=V,A，G 中*些顶点与弧组成的非空有限序列 0v，1a，1v，2a，.，ka，kv 这里0v，.，kvV，iaA，且ia=1iv，iv，则称它为从0v到kv的有向途径。类似的可定义有向迹，有向路，有向闭途径，有向闭迹，有向回路圈等。当 G 时简单有向图时，从0v到kv的一条有向途径可简记为0v，.,kv。二 最短路问题 定义：所谓最短路径是指如果从图中*一顶点称为源点到达另一顶点称为终点 的路径可能不止一条，如何找到一跳有向路径使得沿这条路径上各弧的权值总和最小。2.1 最短路问题的提
11、出*旅客要从乘飞机前往奥地利的萨尔斯堡，因为他害怕乘坐飞机，因此要选择一-条航线，使得在空中飞行的时间尽可能的少。如何选择航线以到达要求。为此构造一个无向网络总可以化成有向网络。设 G=V,A,w是一个有向网络，p 为 G 中一条有向路，称 wP=Paaw)(为路径 p 的路长。现找网络中一条从指定顶点 vi到另一个指定顶点 vj的最短有向路径。三 最短路径算法研究 3.1 Dijkstra 算法 3.11 Dijkstra 算法的根本思想 对网络中每个顶点赋一个标号，用来记录从1v顶点到该顶点的最短路的长度称为永久标号或最短长度的上界称为临时标号。算法开场时，只有顶点1v被赋予永久标号1v=
12、0，其他顶点iv赋予临时标号ijjwu。一般的，算法在被临时标号的顶点中寻找一个顶点kv，其临时标号ku最小，然后将kv赋予永久标号ku，并且对其余临时标号的顶点vj按照方式,minkjkjjwuuu修正其标号。算法在所有顶点被赋予永久标号时完毕。3.12 Dijkstra 算法的理论依据（1）对于 S 中任意一顶点，其永久标号都是从顶点1v到该顶点的最短路的长度。（2）对于 R 中任意一顶点，其临时标号都是从顶点1v出发，只经过 S 中顶点到达该顶点的最短路的长度。3.13 Dijkstra 算法的计算步骤 最短路径问题是指在一个赋予权值的图的两个指定节点0u和 v 之间找出一条具有最小权值
13、的路。Dijkstra 算法是一个解最短路径问题的算法，这个算法不仅可以找到最短的0u，v，路径而且可以给出从0u到图中所有节点的最短路径，-根本步骤如下：（1）设)(0uD=0，对所有节点0uw 来说，设)(wD=，并且将0u标号为 0，0ut，d 为0u和 w 之间的权值距离。（2）按照每个没有标号的节点 w 计算)(wD，),()(),(min)(wtLtDwDwD，),(wtL表示节点 t 到节点 w 之间的权值。如果)(wD标号被修改了说明在当前得到的0u到 w 的最优路径上 t 和 w 相邻，用wt记录下来在所有)(wD中选择一个最小的)(sD即)(min)(wDsD，w 未标号。
14、将 s 标号为)(sD/wt，表示节点0u到s 的最优路径的长度)(sD且wt与 s 相邻。（3）如果重点 v 已经标号，则停顿。得到一条从0u到 v 的最优路径。否则 st，反向。（4）按照上述步骤继续计算。3.14 Dijstre 算法的建模应用举例*城市要在该城市所辖的 8 个区中的1u区建立一个取水点，如下图的是这 8 个区之间的分布以及相邻各区的距离。现要从1u区向其他各区运水，求出1u区到其他各区的最短路径。先写出带权邻接矩阵：W=03064093021509701608120 因为 G 是无向图，所以 W 是对称矩阵。-迭代次数)(iuL 1u 2u 3u 4u 5u 6u 7u
15、 8u 1 0 2 0 2 1 8 3 2 8 10 4 8 3 10 5 8 6 10 12 6 7 10 12 7 9 12 8 12 最后标记 Lv 0 2 1 7 3 6 9 12 Zv 1u 1u 1u 6u 2u 5u 4u 5u 因此得到最短路径为：迭代次数)(iuL 1u 2u 3u 4u 5u 6u 7u 8u 最后标记 Lv 0 2 1 7 3 6 9 12 Zv 1u 1u 1u 6u 2u 5u 4u 5u 由上表可得到1u到各点的最短路径为：-21uu；31uu；41uu，421uuu，431uuu；521uuu；6521uuuu；741uuu，731uuu，7652
16、1uuuuu；8521uuuu，86521uuuuu。上述 Dijkstra 算法的 MATLAB 代码：w=0 2 1 8 inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0 n=size(w,1);w1=w(1,:);%赋初值%for i=1:n l(i)=w1(i);z(i)=1;end s=;s(1)=1;
17、u=s(1);k=1;while kl(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;end end end end l,z%求 v*L1=1;for i=1:n for j=1:k if i=s(j)l1(i)=l1(i);else l1(i)=inf;end end end-lv=inf;for i=1:n if l1(i)lv lv=l1(i);v=i;end end lv,v s(k+1)=v k=k+1 u=s(k)end l,z 3.2 FLOYD 算法 3.21 FLOYD 算法的根本思想 直接在图的带权邻接矩阵中使用插入顶点的方法依次构造出 n 个矩阵)1(
18、D，)2(D.，)(nD，使得最终得到的矩阵)(nD成为图的距离矩阵，并且同时求出插入的点的矩阵以便于得到两点间的最短路径。3.22 FLOYD 算法原理 1FLOYD 算法求路径矩阵的方法：在建立距离矩阵的同时可建立路径矩阵 R。每一次求到一个)(kD时，按照以下的方式产生相应的新)(kR，-即当kv被插入在任何两点间的最短路径时，被记录在)(kR中，依次求)(nR时求得)(nD，可由)(nR来查找任何两个点之间的最短路径。2FLOYD 算法查找最短路径的方法：如果1)(Prnij，则点1p是点i到点j的最短路的中点。用同样的方法再查找，如果：1向点i查找得：2)(1prnip，3)(2pr
19、nip，.，knipprk)(。2向点j查找得：1)(1qrnjp，2)(1qrnjq，.，jrnjqm)(。则从点i到j的最短路径为：i，kp,.,2p，1p，1q，2q，.，mq，j 3.23 FLOYD 算法的算法步骤 Floud 算法算法目的：求任意两个顶点间的最短路径。),(jiD：表示i到j之间的距离。),(jiR：表示i到j之间的插入点。起始：选定带权值的邻接矩阵),(jiw 1赋值：对所有的i，j，),(jid),(jiw，),(jirj，k1。2更新),(jid，),(jir对所有的i，j，如果),(),(),(didjkdkid，则),(),(),(jkdkidjid，kj
20、ir),(。3如果k=v，则算法终止；否则1kk，再次回到 2，以此类推。3.24 FLOYD 建模应用举例*个城市要建立一个消防站，为该城市所属的七个区效劳，如下图。问应该把这个消防站设置在哪个区，才能使该消防站到最远的区的路径最短。用 Floyd 算法求出各点之间的距离，得到表格：1v 2v 3v 4v 5v 6v 7v 1v 0 3 5 10 7 5.5 7-2v 3 0 2 7 4 2.5 4 3v 5 2 0 5 2 4.5 6 4v 10 7 5 0 3 7 8.5 5v 7 4 2 3 0 4 5.5 6v 5.5 2.5 4.5 7 4 0 1.5 7v 7 4 6 8.5 5
21、.5 1.5 0 从上表可以得出距离矩阵 计 算 在 各 点iv设 立 效 劳 设 施 的 最 大 效 劳 距 离)(ivS，7.,3,2,1,max)(1jidvSijvji。10)(1vS，7)(2vS，6)(3vS，5.8)(4vS，7)(5vS，7)(6vS，5.8)(7vS 由于)(),(),(),(),(),(),(min7654321vSvSvSvSvSvSvS=6)(3vS 则应该将消防站设置在3v处。上述 Floyd 算法的 MATLAB 算法代码为：clear：w=0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6
22、,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;inf,inf,inf,1.5,0;d,r=floyd(w)S=ma*(d)%求矩阵各列的最大值 s=min(S)3.3 Dijkstra 算法与 Floyd 算法的比拟 用 Dijkstra 算法解 3.24 的实例。带权的邻接矩阵为：-迭代次数)(ivL 1v 2v 3v 4v 5v 6v 7v 1 0 2 0 3 3 3 5 4.8 5.5 4 5 7.8 5.5 5 7.8 5.5 6 7.8 7 7 7.8 最后标记 )(ivL 0 3 5 7.8 4.8 5.5 7)(ivZ 1v 1v 2v 5v 2v 2v 6v 从上表可以得到1v到各个顶点的最短路径，同理可以得到2v，3v，4v，5v，6v，7v到各个顶点的最短路径。iS表示第顶点iv到其他各顶点的最短路径的路长之和，最后取最小的iS所对应的顶点作为消防站的建立点。从上述方法同样可以得出应该在3v建立消防站的结论。