最短路径问题的算法分析及建模案例

1、最短路径问题的算法分析及建模案例.摘要2.网络最短路径问题的基础知识3有向图5连通性错误！未定义书签。割集错误！未定义书签。最短路问题6.最短路径的算法研究 错误！未定义书签。最短路问题的提出6Bellman 最短路方程 错误！未定义书签。Bellman-Ford算法的基本思想 错误！未定义书签。Bellman-Ford 算法的步骤 错误!未定义书签。实例错误！未定义书签。Bellman-FORD算法的建模应用举例错误！未定义书签。 TOC o 1-5 h z Dijkstra算法的基本思想6Dijkstra算法的理论依据6Dijkstra算法的计算步骤6Dijstre算法的建模应用举例 7两

2、种算法的分析 错误!未定义书签。.Diklstra 算法和Bellman-Ford算法思想有很大的区别错误！未定义书签。Bellman-Ford 算法在求解过程中，每次循环都要修改所有顶点的权值，也就是说源点到各顶点最短路径长度一直要到Bellman-Ford 算法结束才确定下来。错误!未定义书签。.Diklstra 算法和Bellman-Ford算法的限制错误!未定义书签。.Bellman-Ford 算法的另外一种理解错误!未定义书签。.Bellman-Ford 算法的改进错误！未定义书签。摘要近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径问题一直是图论中的一个典型问题，

3、它已应用在地理信息科学，计算机科学等诸多 领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的一个典 型例子。由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究， 使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题的建 模问题中。关键词：计算机 图论交通道路网最短路径A. In this paper,Computer developing rapidly in recent years, graph theory research also have been greatly de

4、veloped, and the shortest path problem is a typical problem in graph theory, it has been applied in geographical information science, computer science, and many other fields. And in the transportation network of the shortest route between two cities in is a typical example of the shortest path probl

5、em.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 suggest some algorithm and the algorithm of the shortest path proble

6、m between the comparison, finally the algorithm is applied to the modeling of the actual problem again.Key words: computer graph traffic road network The shortest path前言最短路径问题是图论以及运筹学中的一个非常重要的问题，在生产实践，运输及工程建筑等方面有着十分广泛的应用。本文对图论中的最短路径问题进行分析， 对其运算解法进行分析寻求比较快捷的模型解法；主要解决的是从某个顶点到其 余各个顶点的最短路径问题。本文从 Floyd算法

7、以及Dijkstra 算法两种算法入 手，概述了这两种方法的原理，提出了求解最短路径问题的算法思想， 并且对两 种算法进行分析比较，提出改进的方法。网络最短路径问题的基础知识图1图图G是一个（无向）图，其中有序二元组（V,E） , V=vi, v2,. vn是顶点集，E= 0 是集，0是一个无序二元组 Vi , Vj 它表示该边连接的是顶点Vi ,Vj。图1就是一个图注释：图形的大小，位置，形状是无关紧要的。若q = Vi, Vj则称eij连接Vi和Vj ;点m和Vj称为0的顶点，Vi和Vj是邻接的顶点；如果两条边有公共的一个顶点，则称这两边是邻接的。无环图定义：没有环的图称之为无环图。简单图

8、定义：没有环且没有重边的图称之为简单图。设6= (V,E)是一个简单图，则有|E|不大于|V| (|V|-1 ) /2完全图定义：若上式的等号成立那么该图中每对顶点恰好有一条边相连，则称该图为完全图。有向图 定义：一个有向图G是一个有序二元组(V,A) , V=vV2, ., vn是顶点集，A= a。称为G的弧集，aij为有序二元组称a。为m连向Vj的弧，a。为m的出弧，Vj的入弧；Vi称为a。的得尾，V。称为aj个有向图。个有向图。环定义：头尾重合的弧称为环。简单有向图定义：没有环和重弧的有向图称为简单有向图。完全有向图定义：设G= (V,E)是一个简单有向图，则|A|不大于|V| (|V|

9、-1 ),若等号成 立则称这样的图为完全有向图。途径，迹，路定义:设图G= (V,E),若它的某些顶点与边可以排成一个非空的有限交错序列定义:(Vo, 8, V1,. ek, Vk)，这里该途径中边互不相同，则称为迹；如果顶点互不相同，则称之为路。显然路必为迹，但反之不一定成立。连通图 定义：图G中如果存在一条从顶点w到Vj的途径，则称m和Vj是连通的。如果图G中任何两个顶点都是连通的，则称 G是连通图。有向途径定义：设有一个有向图G= (V,A) , G中某些顶点与弧组成的非空有限序列(Vo , ai , vi , a2 , . , ak , vk)这里v0, . , vk V, a A,且

10、alVr, Vj),则称它为从v0到vk的有向途 径。类似的可定义有向迹，有向路，有向闭途径，有向闭迹，有向回路(圈)等。 当G时简单有向图时，从vo到vk的一条有向途径可简记为(vo, .,vk)。二最短路问题定义：所谓最短路径是指如果从图中某一顶点(称为源点)到达另一顶点(称为 终点)的路径可能不止一条，如何找到一跳有向路径使得沿这条路径上各弧的权 值总和最小。2.1最短路问题的提出某旅客要从杭州乘飞机前往奥地利的萨尔斯堡，因为他害怕乘坐飞机，因此要选择一条航线，使得在空中飞行的时间尽可能的少。如何选择航线以达到要求。 为此构造一个无向网络总可以化成有向网络。设G= (V,A,w)是一个有

11、向网络，p为G中一条有向路，称w (P) = w(a)为路 a P径p的路长。现找网络中一条从指定顶点 vi到另一个指定顶点vj的最短有向路 径。三最短路径算法研究Dijkstra 算法Dijkstra算法的基本思想对网络中每个顶点赋一个标号，用来记录从丫1顶点到该顶点的最短路的长度(称 为永久标号)或最短长度的上界(称为临时标号)。算法开始时，只有顶点必被赋予永久标号=0,其他顶点vi赋予临时标号Uj wj。一般的，算法在被临时标 号的顶点中寻找一个顶点vk,其临时标号uk最小，然后将vk赋予永久标号uk, 并且对其余临时标号的顶点vj按照方式Uj minUj,uk wkj修正其标号。算法在

12、 所有顶点被赋予永久标号时结束。Dijkstra算法的理论依据(1)对于S中任意一顶点，其永久标号都是从顶点M到该顶点的最短路的长度。(2)对于R中任意一顶点，其临时标号都是从顶点 %出发，只经过S中顶点到达该顶点的最短路的长度。3.13 Dijkstra算法的计算步骤最短路径问题是指在一个赋予权值的图的两个指定节点u0和v之间找出一条具有最小权值的路。Dijkstra 算法是一个解最短路径问题的算法，这个算法不仅 可以找到最短的(uo, v),路径而且可以给出从Uo到图中所有节点的最短路径， 基本步骤如下：(1)设D(Uo)=O,对所有节点w Uo来说，设D(w)=，并且将u0标号为0, u

13、0-t, d为u0和w之间的权值(距离)。(2)按照每个没有标号的节点 w计算D(w), D(w) min D(w),D(t) L(t,w),L(t,w)表示节点t到节点w之间的权值。如果D(w)标号被修改了说明在当前得到的u0到w的最优路径上t和w相邻，用tw记录下来在所有D(w)中选择一个最小的D(s)即D(s) minD(w) , w未标号。将s标号为D(s)/tw,表示节点u0到 s的最优路径的长度D(s)且tw与s相邻。(3)如果重点v已经标号，则停止。得到一条从u0到v的最优路径。否则s-t, 反向。(4)按照上述步骤继续计算。3.14 Dijstre算法的建模应用举例某城市要在该

14、城市所辖的 8个区中的5区建立一个取水点，如图所示的是这8个区之间的分布以及相邻各区的距离。 现要从Ui区向其他各区运水，求出Ui区到 其他各区的最短路径。11先写出带权邻接矩阵:0 2 1806 19W=1 2W=390 4 60 30因为G是无向图，所以W是对称矩阵。迭代次 数L(uJU1U2U3U4U5U6U7U81020218328104831058610126710127912812最后标 记L (v)021736912Z (v)UiUiUiU6U2U5U4U5因止匕得至1最短路径为：迭代次 数L(uJUiU2U3U4U5U6U7U8最后标 记L (v)02i7369i2Z (v)U

15、iUiUiU6U2U5U4U5由上表可得到U1到各点的最短路径为:UiU2 ；UiU3 ;Ui UUi U4 , UiU2 U4, UiU3 U4;UiU2U5 ;UiU2U5 U6 ；Ui Ui U4 U7 , UiU3U7 , UiU2 U5 U6U7 ；Ui Ui U2 U5 U8, UiU2U5U6U8。上述 Dijkstra 算法的 MATLAB:w=0 2 i 8 inf inf inf;2 0 inf 6 i inf inf inf ;i inf 0 7 inf inf 9 inf;8 6 7 0 5 i 2 inf;inf i inf 5 0 3 inf 9;inf inf i

16、nf i 3 0 4 6;inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0 n=size(w,i);wi=w(i,:);% 赋初值 %for i=i:nl(i)=wi(i);z(i)=i;ends=;s(i)=i;U=s(i);k=i;while kl(u)+w(u,i) l(i)=l(u)+w(u,i); z(i)=u;endend endend l,z %求v* L1=1; for i=1:n for j=1:k if i=s(j) l1(i)=l1(i); elsel1(i)=inf;endend end lv=inf; for i=1:n if

17、 l1(i)lv lv=l1(i); v=i;end end lv,v s(k+1)=v k=k+1 u=s(k) end l,zFLOYD 算法FLOYD算法的基本思想直接在图的带权邻接矩阵中使用插入顶点的方法依次构造出n个矩阵D，D，D，使得最终得到的矩阵D成为图的距离矩阵，并且同时求出插入的点的矩阵以便于得到两点间的最短路径。FLOYD算法原理(D floyDT法求路径矩阵的方法：在建立距离矩阵的同时可建立路径矩阵 R。(0)(0).R (rij ) v v, rijJ每一次求到一个D(k)时，按照下列的方式产生相应的新R(k),(k) r (k) r ijk若d：(k 1),(k 1)

18、 dik否则,(k 1) dkj即当Vk被插入在任何两点间的最短路径时，被记录在R(k)中，依次求R时求得D，可由R来查找任何两个点之间的最短路径。FLOYDT法查找最短路径的方法：如果rj(n)P ,那么点Pi是点i到点j的最短路的中点。用同样的方法再查找，如果：(1)向点i查找得：韬P2, %) P3,., ip/Pk。(2)向点 j 查找得：rp1j(n) q,1 q2, . , j。那么从点i到j的最短路径为：i,pk,., p2 , p1 ,q1,q2, . ,qm ,ji PkP3P2Pl fll A2 qin JFLOYD算法的算法步骤Floud算法算法目的：求任意两个顶点间的最

19、短路径。D(i, j)：表示i到j之间的距离。R(i, j):表示i到j之间的插入点。起始：选定带权值的邻接矩阵 w(i,j)(1)赋化 对所有的 i , j , d(i, j)w(i, j) , r(i, j) j , k 1。(2)更新 d(i,j), r(i,j)对所有的 i , j ,如果 d(i,k) d(k, j) d(i,d),那么 d(i, j) d(i,k) d(k, j) , r(i,j) k。(3)如果k=v,那么算法终止；否则k k 1,再次回到(2),以此类推FLOYD建模应用举例某个城市要建立一个消防站，为该城市所属的七个区服务，如图所示。问应该把 这个消防站设置在

20、哪个区，才能使该消防站到最远的区的路径最短。用Floyd算法求出各点之间的距离，得到表格:ViV2V3V4V5V6V7Vi0351075.57V2302742.54V3520524.56V410750378.5V57423045.5V65.52.54.57401.5V77468.55.51.50从上表可以得出距离矩阵D d(j)7 730252010757423025201075742 TOC o 1-5 h z 742.54524.560378.53045.55.5 2.5 4.5 745.5 2.5 4.5 740 1.5468.5 5.5 1.5 0计算在各点Vi设立服务设施的最大服务距离S(vi),鼠,)maxdj, i,j 1,2,3.,7。1 j v JS(vi) 10, S(V2