迪克斯屈拉最短路径算法图论论文

姓名：沈敬红学院：通信学院学号：s1401311091计算机网络中迪克斯屈拉最短路径算法的程序实现及应用沈敬红S140131109重庆邮电大学通信与信息工程学院摘要：本文首先介绍了图论的发展历程，介绍了图论在实际问题中的应用。其次，介绍了图论中最短路径的问题及相关内容，介绍了计算机网络中服务器之间存在的最短路径问题。然后，介绍了迪克斯屈拉（Dijkstra）最短路径算法。最后，依据算法的思想，分别实现了Dijkstra算法在求解计算网络最短路径的应用程序。关键词：最短路径服务器Dijkstra算法程序Abstractinthispaper,wefirstlyintroducetheprocessoftheoryofgraph.secondly,wegivetheintroductionoftheproblemofshortestpathandrelatedcontent,andtheapplicationofnetworkswhichalotofsevershavetosearchtheshortestpath.Andthenshowstheoneofshortestpathalgorithms:TheDijkstraalgorithm.Finally,accordingtotheideasofthisalgorithm,weputforwardamethodtoachievetheprocedureusinginthenetworks.KeywordShortest—pathsSeverDijkstraProgram1、引言图论(GraphTheory)是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。图论的发展已有200多年的历史，它发源于18世纪普鲁士的柯尼斯堡。当地的居民想知道能否从任意一陆地出发，走遍联接该城的7座桥又回到原地?其条件是每座桥都经过一次并且只经过一次。（具体见“七桥问题”）在加权连通图中，寻求最短路径的问题有其实际背景，例如在某一国家或地区，城市与城市之间都互相连通，从一个城市到达另一城市存在着多条路径，如何实现最短的路径完成两个城市之间的货物运输就是一个解决图论中实现最短路径的问题。同样，比如需要架设电网、通信网络以及其他的有线网络，基于全网的考虑之下，点和点之间怎样架设一条最短的线路就是一个实际的最短路问题。按照图论的表述，在一个图中，两点之间的路径可能有很多条，且每条路径所经过的边数可能是不同的，如果是网络，每条路径的各边权数之和也可能是不同的，怎样找到一条顶点对顶点之间的各边权数之和为最小的路径问题称为最短路问题[1]。本文提出了一个计算机网络中服务器之间最短路径的问题背景，并在迪克斯屈拉（Dijkstra）算法的基础上，实现算法在服务器之间寻求最短路径的程序设计。姓名：沈敬红学院：通信学院学号：s14013110922、图论相关概念[1,2]：无向图：每一条边都是无向边的图称为无向图。链：设u和v是任意图G的顶点，图G的一条u-v链（chain或walk）是有限的顶点和边交替的序列u0e1u1e2…un-1enun(u=u0,v=un),其中与边e（1≤i≤n）相邻的两个顶点ui和ui-1正好是ei的两个端点。路：内部点不同的链称为路（path）。圈：两端点相同的路（即闭路）称为圈或回路。加权图：边上有数的图称为加权图（weightedgraph）。若边e标记数为k，则称边e的权(weight)为k。在加权图中，链（迹、路）的长度为链（迹、路）上的所有边的权值之和.邻接矩阵：设G＝V,E是任意图，规定n阶方阵A=（aij）为G的邻接矩阵，其中aij为图G中以xi为起点且以yj为终点的边的数目。边权矩阵：设G＝V,E是n阶加权简单图，规定D=（dij）m×n是图的加权矩阵，即dij＝w（i，j）。若结点i到结点j无边可连（在有向图中是方向不一致）时，取dij＝∞。3、问题描述在现有的Internet中存在着大量的不同种类的服务器[7]，这些服务器为用户提供不同种类的数据服务，在服务器与服务器之间存在着数据的交流。如果，我们将各个服务器看做是一个顶点，将服务器与服务器之间的链接看做是一条边，则服务器组成的网络就是一个无向连通图[9]。在这个图上，服务器与服务器之间的链路上都存在着一定的时延，由于网络环境的不同，每个边上的时延均不相同，有的只有几十毫秒，有的却达到上百毫秒，这些毫秒数就可以看做边的权值，如何选择最佳的路径使得服务器与服务器之间的数据交换所需时间最短的问题，就变成了求解在无向连通加权图中寻求最短路径的问题。如下图为网络服务器之间的拓扑图：（注：S1-S6为网络服务器节点，权值为10ms/每单位值）4、迪克斯屈拉（Dijkstra）算法实现4.1Dijkstra算法[1]描述：算法基本思想：一个顶点V1作为源点，求该顶点到其他各顶点的最短路径，迪克斯屈拉提出了一个按路径长度递增的顺序产生最短路径的方法。此方法的基本姓名：沈敬红学院：通信学院学号：s1401311093思想是：把图中所有结点分成两组，第一组包括已确定最短路径的顶点，第二组包括尚未确定最短路径的顶点，按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中，直到从V1出发可以到达的所有顶点都已包括在第一组中。在这过程中，总保持从V1到第一组各顶点的最短路径都不大于从V1到第二组的任何顶点的最短路径长度。另外，每个顶点对应一个距离值，第一组的顶点对应的距离值就是从V1到此顶点的最短路径长度，第二组的顶点对应的距离值是从V1到此顶点的只包括第一组的顶点为中间顶点的最短路径长度[2]。实现过程描述：一开始第一组只包括顶点V1，第二组包括其他所有顶点。V1对应的距离值为0，第二组的顶点对应的距离值是这样确定的：若图中有弧〈V1，Vj〉，则Vj的距离为此弧的权值，否则Vj的距离为∞（或用一个很大的数表示）。然后每次从第二组的顶点中选一个其距离值为最小Vm的加入到第一组中，每往第一组中加入一个顶点Vm，就要对第二组中的各个顶点的距离值进行一次修正。若加进Vm做中间结点，使从V1到Vj的最短路径比不加Vm的路径要短，则要修改Vj的距离值。修改后再选距离值最小的顶点加入到第一组中。如此进行下去，直到图中所有顶点都包括在第一组中，或再也没有可加入到第一组中的顶点存在为止。4.2Dijkstra算法对问题描述及实现：六个服务器节点S1、S2、S3、S4、S5和S6，分别如图表示，各个端点之间的权值标于节点间的联线之上。.G=(V,E)（1）此有加权图的邻接矩阵表示为：（2）对上述问题实现迪克斯屈拉算法的程序过程表述为：有邻接矩阵adjacent表示，若〈S1，Sj〉是图中的弧，则adjacent[i，j]的值等于边上所带的权值，否则adjacent[i，j]等于一个很大的正数infinity_value(在程序中用9999表示)。开始时姓名：沈敬红学院：通信学院学号：s1401311094adjacent[i，j]＝0表示顶点j未在第一组中，处理中用s[j]＝1标志第j个顶点已进入第一组。边的权值为adjacent对应的位置的值，数组元素的下标等于相关联顶点序号。数组distance_shortest[n]的每个元素为顶点的距离值，pre_node[n]的每个元素为从V1到该顶点的路径上此顶点的前一个顶点的序号，若从V1到该顶点无路径，则用0作为其前一个顶点序号。算法结束时，沿着顶点Vj对应的pre_node[j－1]追溯，就能确定V1到Vj最短路径，其最短路径长度等于distance_shortest[j－1]。此算法起始顶点也可以不是V1，起始顶点的序号由变量k给出（即从顶点Vk出发）。源点为Vk(其中k为1)（3）解决上述问题迪克斯屈拉程序源代码为：#includeiostreamusingnamespacestd;//定义常量#definemaxnum50//最大节点数目#defineinfinity_value9999//无穷大值//定义数组，用于存放集合中的数据intdistance_shortest[maxnum];//存放当前节点到达源节点的最短路径值intpre_node[maxnum];//存放当前点的前一个节点intadjacent[maxnum][maxnum];//邻接阵，存放边值intn;//节点个数//Dijkstra算法函数//n节点个数，source源节点voidDijkstra(intn,intsource,int*distance_shortest,int*pre_node,intadjacent[maxnum][maxnum]){bools[maxnum];//定义存放点的集合//初始化for(inti=1;i=n;i++){distance_shortest[i]=adjacent[source][i];//赋值s[i]=0;//将集合置为空if(distance_shortest[i]==infinity_value){pre_node[i]=0;}elsepre_node[i]=1;}s[source]=1;//source加入集合distance_shortest[source]=0;//初始值为0姓名：沈敬红学院：通信学院学号：s1401311095//开始迭代，迭代n-1次for(i=2;i=n;i++){inttemp=infinity_value;intu=source;//找出还未使用的点j的到源的最小路径中distance_shortest[j];for(intj=1;j=n;j++){if((s[j]==0)&&(distance_shortest[j]temp)){u=j;//保存最小值的号temp=distance_shortest[j];}}s[u]=1;//加入最短路径的点//更新distance_shortestfor(j=1;j=n;j++){if((s[j]==0)&&(adjacent[u][j]infinity_value)){intnewdist=distance_shortest[u]+adjacent[u][j];if(newdistdistance_shortest[j]){distance_shortest[j]=newdist;pre_node[j]=u;}}}}}//统计路径函数voidsearchPath(int*pre_node,intsource,intdestination){intque[maxnum];intord=1;que[ord]=destination;ord++;inttmp=pre_node[destination];while(tmp!=source){姓名：沈敬红学院：通信学院学号：s1401311096que[ord]=tmp;ord++;tmp=pre_node[tmp];}que[ord]=source;for(inti=ord;i=1;--i)if(i!=1)coutque[i]-;elsecoutque[i]endl;}voidmain(){cout请输入图的节点的个数：endl;cinn;intp,q,len,num;//输入p,q两端点及其路径长度len，num为要统计的源端点//初始化adjacent[][]为infinity_valuefor(inti=1;i=n;++i)for(intj=1;j=n;++j)adjacent[i][j]=infinity_value;//录入图的边权值cout请按规则依次输入