图论论文--最短路径算法应用

《图论论文--最短路径算法应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程论文课程名称最短路径算法应用-】:短路径游览校园名号都喜欢上了学校。而且经常有同学来找遇到了一个问题：怎样走最短路径來游运用图论屮的一些知识，找到一个最短赋权图等知识，把学校里面我们经常去摘要：重邮是个美丽的学校，我们考入重邮后，我玩，作为他们的导游，在带领他们游览学校时候，览学校最多的景点。当学完图论后，我找到了答案，最有效的路径从而迅速到达某个地点。本文运用了图论中的最短路径算法，邻接矩阵，的地方选了出来，画出平面图，建模赋权图，模拟了在任意两点之间的最短路径的实现以及编程显水。关键词：数据结构；最短路径；迪杰斯特拉算法；一：背景介绍设计学校的校园平面图，

2、所含景点不少于8个（中心食堂、信科、图书馆……）1）带领同学们从新大门开始利用最短路径游览学校的几个景点。2）为來访同学提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。3）在社会生活中，最短距离的运用相当广泛。除了该课题外，还有于此相关的城市道路的设计，交通线路的设计，旅游景点的设计等等。除了路径长度方而外，到两地花费的最少、时间的最短等等都是同样的道理。二：最短路径知识点边上有数的图称为加权图，在加权图中我们经常找到两个指定点间最短路径，称为最短路径问题。在最短路问题中，给出的是一有向加权图G=（V,E）,在其上定义的加权函数W:EtR为

3、从边到实型权值的映射。路径P=（vo,v1（…,vj的权是指其组成边的所有权值之和：w（7?）=乞w（匕—,匕）1=1定义U到V间最短路径的权为min{w（>v}女FI果存在由”到vfl勺通路OO如果不存在从结点U到结点V的最短路径定义为权=的任何路径。①边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。三:Warshall算法介绍我们可以利用Warshall算法來解决最短路径问题。Marshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的

4、关系矩阵为1：（1）置新矩阵A二M;（2）置k=l;（3）对所有i如果A[i,k]=l,则对j=l..n执行：A[i,j]—A[i,j]VA[k,j];(4)k增1;(5)如果kWn,则转到步骤(3),否则停止。所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。设关系R的关系图为G,设图G的所有顶点为vl,v2,-,vn,则t(R)的关系图可用该方法得到：若G屮任意两顶点vi和vjZ间有一条路径且没有vi到vj的弧，则在图G中增加一条从vi到vj的弧，将这样改造后的图记为G',则G'即为t(R)的关系图。G'的邻接矩阵A应满足：若图G中存在从vi到vj路径，即

5、vi与vj连通，则A[i,j]=l,否则A[i,j]=0o这样，求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。定义一个n阶方阵序列A(O),A(1),A(2),…，A(n),每个方阵中的元素值只能取0或loA(m)[i,j]=l表示存在从vi到vj且中间顶点序号不大于m的路径(m=l..n),A(m)[i,j]=0表示不存在这样的路径。而A(0)[i,j]=l表示存在从vi到vj的弧，A(0)[i,j]=0表示不存在从vi到vj的弧。这样，A(n)[i,j]二1表示vi与vj连通，A(n)[i,j]=0表示vi与vj不连通。故A(n)即为t(R)的关系

6、矩阵。那么应如何计算方阵序列A(0),A(l),A(2),…，A(n)呢？很显然，A(0)=M(M为R的关系矩阵)。若A(0)[i,1]=1且A(0)[l,j]=l,或A(0)[i,j]=l,当且仅当存在从vi到vj且中间顶点序号不大于1的路径，此时应将A(l)[i,j]置为1,否则置为0。一般地,若A(k-l)[i,k]=l且A(k-l)[k,j]=l,或A(k-l)[i,j]=l,当且仅当存在从vi到vjll中间顶点序号不大于k的路径，此时应将A(k)[i,j]置为1,否则置为0(k二l..n)。用公式表示即为：A(k)[i,j]=(A(k-l)[i,k]AA

7、(k-l)[k,j])VA(k-l)[i,j]i,j,k=l..n这样，就可得计算A(k)的方法：先将A(k)赋为A(k-l)；再对所有i二l..n,若A(k)[i,k]=l(即A(k-1)[i,k]=l),则对所有j=l..n,执行：A(k)[i,j]^-A(k)[i,j]VA(k-l)[k,j]但这与前述Warshall算法中的第(3)步还有一定距离。若将上式改为：A(k)[i,j]-A(k)[i,j]VA(k)[k,j](即把A(k-1)[k,j]改为A(k)[k,j])就可将上标k去掉，式子就可进一步变为：A[i,j]-A[i,j]VA[k,j]这样可以只

8、用存储一个