图论论文

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

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

3、为从边到实型权值的映射。路径P=(v0, v1, vk)的权是指其组成边的所有权值之和：定义u到v间最短路径的权为从结点u到结点v的最短路径定义为权的任何路径。边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。三：Warshall算法介绍 我们可以利用Warshall算法来解决最短路径问题。Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M： （1）置新矩阵A=M; （2）置k=1; （3）对所有i如果Ai,k=1，则对j=1.n执行： Ai,jAi

4、,jAk,j; （4）k增1; （5）如果kn，则转到步骤（3），否则停止。 所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。设关系R的关系图为G，设图G的所有顶点为v1,v2,vn，则t(R)的关系图可用该方法得到：若G中任意两顶点vi和vj之间有一条路径且没有vi到vj的弧，则在图G中增加一条从vi到vj的弧，将这样改造后的图记为G，则G即为t(R)的关系图。G的邻接矩阵A应满足：若图G中存在从vi到vj路径，即vi与vj连通，则Ai,j=1，否则Ai,j=0。 这样，求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。 定义一个n阶方阵序列A(0),A(1),A(2),A(n)

5、，每个方阵中的元素值只能取0或1。A(m)i,j=1表示存在从vi到vj且中间顶点序号不大于m的路径（m=1.n），A(m)i,j=0表示不存在这样的路径。而A(0)i,j=1表示存在从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)的关系矩阵。 那么应如何计算方阵序列A(0),A(1),A(2),A(n)呢？ 很显然，A(0)=M（M为R的关系矩阵）。 若A(0)i,1=1且A(0)1,j=1，或A(0)i,j=1，当且仅当存在从vi到vj且中间顶点序号不大于1的路径，此

6、时应将A(1)i,j置为1，否则置为0。 一般地，若A(k-1)i,k=1且A(k-1)k,j=1，或A(k-1)i,j=1，当且仅当存在从vi到vj且中间顶点序号不大于k的路径，此时应将A(k)i,j置为1，否则置为0（k=1.n）。用公式表示即为： A (k)i,j=(A(k-1)i,kA(k-1)k,j)A(k-1)i,j i,j,k=1.n 这样，就可得计算A(k)的方法：先将A(k)赋为A(k-1)；再对所有i=1.n，若A(k)i,k=1（即A(k-1)i,k=1），则对所有j=1.n，执行： A (k)i,jA(k)i,jA(k-1)k,j 但这与前述Warshall算法中的第（

7、3）步还有一定距离。若将上式改为： A(k)i,jA(k)i,jA(k)k,j （即把A(k-1)k,j改为A(k)k,j） 就可将上标k去掉，式子就可进一步变为： Ai,jAi,jAk,j 这样可以只用存储一个n阶方阵的空间完成计算，且与前述Warshall算法中第（3）步的式子一致。那么，可不可以把A(k-1)k,j改为A(k)k,j呢？答案是肯定的。下面将证明在计算A(k)的过程中A(k-1)k,j与A(k)k,j相等（A(k)被赋初值A(k-1)后）。考察计算A(k)的方法 只有当i=k时A(k)k,j的值才有可能改变，此时将式A(k)i,jA(k)i,jA(k-1)k,j中的i换为k

8、，得A(k)k,jA(k)k,jA(k-1)k,j，对某一j，执行该式的赋值操作前A(k)k,j=A(k-1)k,j，因为计算A(k)开始时A(k)被赋为A(k-1)，故它们相或的结果等于A(k-1)k,j，故赋值操作不改变A(k)k,j的值。这样，就没有操作会改变A(k)k,j的值，故A(k-1)k,j与A(k)k,j相等。 综上，就可得到计算A(n)的算法，且该算法与前述的Warshall算法完全一致。 由上面的分析，不难看出，Warshall算法类似于求图中每对顶点间最短路径的Floyd算法。其实，用Floyd算法也能求关系的传递闭包，方法为令关系R的关系图G中的每条弧的权值都为1，这样

9、得一有向网G1，设G1的邻接矩阵为D(-1)（若vi无自回路，则D(-1)(i,i)=），对G1用Floyd算法求其每对顶点间最短路径，得结果矩阵D(n-1)。因若G中vi与vj连通，当且仅当D(n-1)i,j，故将矩阵D中的都改为0，其它值都改为1，得矩阵A，则矩阵A即为t(R)的关系矩阵。Floyd算法和Warshall算法的时间复杂度都为O(n3)，但明显用Floyd算法求关系的传递闭包绕了弯子。四：算法实现本文主要以我们学校为模型，选取几处比较典型的建筑分别为：学校新大门、数字图书馆、重邮宾馆、信科大厦、老图书馆、二教、中心食堂、三教、逸夫科技楼、外国语学院。建筑物之间的路径用直线连接

10、，线上的数字表示两景点间的距离。抽象的平面图如下所示：新校门数字图书馆逸夫科技楼三教二教中心食堂信科大厦重邮宾馆图书馆2060103015704015901002025外语学院图2 我校主要建筑分布图运用图论知识对上图进行邻接矩阵的表示，为了方便表示我对上图的地点：新校门代号为1，数字图书馆代号为2，重邮宾馆代号为3，信科大厦代号为4，图书馆代号为5二教学楼代号为6，中心食堂代号为7，逸夫科技楼代号为8，三教学楼代号为9，外国语学院代号10。邻接矩阵D如下图： 四：算法分析 问题描述用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道

11、路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。游客通过终端可询问： 从某一景点到另一景点的最短路径。(最短路径问题)游客从新校门口进入，选取一条最佳路线。 基本要求将导游图看作一张带权无向图，顶点表示学校的各个景点，边表示各景点之间的道路，边上的权值表示距离为此图选择适当的数据结构。把各种路径都显示给游客，由游客自己选择浏览路线。画出景点分布图于屏幕上。 实现提示 首先构造一个无向图G并用邻接矩阵来存储。分别当k=1,2,3,4,5,6,7,8,9,10时，利用Warshall算法来化简邻接矩阵，最后k=10时，得到的矩阵就是所求。五：程序实现本文运用了Warshall算法

12、，其抽象算法为：#include using namespace std;const int size=4;void print(int asize)for(int k=0;ksize;k+)for (int l=0;lsize;l+)coutakl ;if (l=size-1)coutendl;coutnn;void transform(int asize,int bsize) int i,j,k; for(i=0;isize;i+) for(j=0;jsize;j+) bij=aij;for(k=0;ksize;k+)for(i=0;isize;i+)for(j=0;jsize;j+)if

13、(bik=1&bki=1)|bij=1)bij=1;coutM k+1 =:endl;print(b);int main()int msizesize;int mtsizesize;/初始化；for(int i=0;isize;i+)for (int j=0;jsize;j+)mij=0;/输入R的关系矩阵；int a,b;cout输入R的关系矩阵：（输入元素为1的行与列）endl;int choice;cout选择：1（继续输入）0（终止）choice;while (choice)couta;coutb;ma-1b-1=1;cout选择：1（继续输入）0（终止）choice;cout关系矩阵

14、R为：endl;print(m);transform(m,mt);return 0;六：运行结果分析基于以上核心算法加上运用对二维数组以及链表的操作完成了此功能，本程序是运行于dos显示没有运用mfc界面编程，掌握了一些基础知识以后，基本可以完成本实验。本设计中只是完成了要求的内容，并没有考虑算法的时间复杂度，然而这些也是图论所介绍过的，在大程序中就显得的非常重要了，但是本例考虑程序小为了实现方便没有予以考虑，特别是在显示任意两节点的所有可行的方法上，对于五个结点的计算复杂度达到了O（n*n*n*n*n）的程度，这在以后的编程中需要注意的。七：总结经过此次的图论的课程报告，使我对于图论，特别是

15、图论中的最短路径算法有了深刻的了解，也使我对于编程的能力有所提高。图论是生活技巧的一门学问，里面很多经典算法。把理论运用于实践能得到意想不到的乐趣，感觉这也是做学问的真是内涵所在。同时我也认识到了自己的不足，对于理论知识学习的不扎实，还需要借助工具书课本，对于编程也需要参考才能最后自己实现，可见，学海无涯，需要学习的东西还有很多。感谢张清华老师的指导教学，在一会的日子里我会更加努力的学习，不仅学习理论，还有把理论运用于实践之中。参考文献：2006年全国信息学冬令营讲座最短路算法及应用蒋长浩，吴建专，顾国华，殷翔图论及其应用，东南大学出版社，2002年。徐俊明图论及其应用，中国科学与技术大学出版社，2000年。殷剑宏、吴开亚主编，图论及其算法，中国科学技术大学出版社，2005 年。G.PerryC+程序设计教程， 清华大学出版社，1994。张选平、雷咏梅主编，数据结构，机械工业出版社，2001 年。