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

姓名：沈敬红 学院：通信学院 学号：s140131109计算机网络中迪克斯屈拉最短路径算法的程序实现及应用沈敬红 S140131109重庆邮电大学通信与信息工程学院摘要：本文首先介绍了图论的发展历程，介绍了图论在实际问题中的应用。其次，介绍了图论中最短路径的问题及相关内容，介绍了计算机网络中服务器之间存在的最短路径问题。然后，介绍了迪克斯屈拉（Dijkstra）最短路径算法。最后，依据算法的思想，分别实现了Dijkstra算法在求解计算网络最短路径的应用程序。关键词：最短路径 服务器 Dijkstra算法 程序Abstract in this paper, we firstly introduce the process of theory of graph. secondly, we give the introduction of the problem of shortest path and related content, and the application of networks which a lot of severs have to search the shortest path. And then shows the one of shortest path algorithms: The Dijkstra algorithm. Finally, according to the ideas of this algorithm, we put forward a method to achieve the procedure using in the networks.Key word Shortestpaths Sever Dijkstra Program1、引 言图论(Graph Theory)是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。图论的发展已有200多年的历史，它发源于18世纪普鲁士的柯尼斯堡。当地的居民想知道能否从任意一陆地出发，走遍联接该城的7座桥又回到原地? 其条件是每座桥都经过一次并且只经过一次。（具体见“七桥问题”）在加权连通图中，寻求最短路径的问题有其实际背景，例如在某一国家或地区，城市与城市之间都互相连通，从一个城市到达另一城市存在着多条路径，如何实现最短的路径完成两个城市之间的货物运输就是一个解决图论中实现最短路径的问题。同样，比如需要架设电网、通信网络以及其他的有线网络，基于全网的考虑之下，点和点之间怎样架设一条最短的线路就是一个实际的最短路问题。按照图论的表述，在一个图中，两点之间的路径可能有很多条，且每条路径所经过的边数可能是不同的，如果是网络，每条路径的各边权数之和也可能是不同的，怎样找到一条顶点对顶点之间的各边权数之和为最小的路径问题称为最短路问题1。本文提出了一个计算机网络中服务器之间最短路径的问题背景，并在迪克斯屈拉（Dijkstra）算法的基础上，实现算法在服务器之间寻求最短路径的程序设计。2、图论相关概念1,2：无向图：每一条边都是无向边的图称为无向图。链：设u和v是任意图G的顶点，图G的一条u-v链（chain或walk）是有限的顶点和边交替的序列u0e1u1e2un-1enun(u=u0,v=un),其中与边e（1in）相邻的两个顶点ui和ui-1正好是ei的两个端点。路：内部点不同的链称为路（path）。圈：两端点相同的路（即闭路）称为圈或回路。加权图：边上有数的图称为加权图（weighted graph）。若边e标记数为k，则称边e的权(weight)为k。在加权图中，链（迹、路）的长度为链（迹、路）上的所有边的权值之和.邻接矩阵：设G是任意图，规定n阶方阵A=（aij）为G的邻接矩阵，其中aij为图G中以xi为起点且以yj为终点的边的数目。边权矩阵：设G是n阶加权简单图，规定D=（dij）mn是图的加权矩阵，即dijw（i，j）。若结点i到结点j无边可连（在有向图中是方向不一致）时，取dij。3、问题描述在现有的Internet中存在着大量的不同种类的服务器7，这些服务器为用户提供不同种类的数据服务，在服务器与服务器之间存在着数据的交流。如果，我们将各个服务器看做是一个顶点，将服务器与服务器之间的链接看做是一条边，则服务器组成的网络就是一个无向连通图9。在这个图上，服务器与服务器之间的链路上都存在着一定的时延，由于网络环境的不同，每个边上的时延均不相同，有的只有几十毫秒，有的却达到上百毫秒，这些毫秒数就可以看做边的权值，如何选择最佳的路径使得服务器与服务器之间的数据交换所需时间最短的问题，就变成了求解在无向连通加权图中寻求最短路径的问题。如下图为网络服务器之间的拓扑图：（注：S1-S6为网络服务器节点，权值为10ms/每单位值）4、迪克斯屈拉（Dijkstra）算法实现4.1 Dijkstra算法1描述： 算法基本思想：一个顶点V1作为源点，求该顶点到其他各顶点的最短路径，迪克斯屈拉提出了一个按路径长度递增的顺序产生最短路径的方法。此方法的基本思想是：把图中所有结点分成两组，第一组包括已确定最短路径的顶点，第二组包括尚未确定最短路径的顶点 ，按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中，直到从V1出发可以到达的所有顶点都已包括在第一组中。在这过程中，总保持从V1到第一组各顶点的最短路径都不大于从V1到第二组的任何顶点的最短路径长度。另外，每个顶点对应一个距离值，第一组的顶点对应的距离值就是从V1到此顶点的最短路径长度，第二组的顶点对应的距离值是从V1到此顶点的只包括第一组的顶点为中间顶点的最短路径长度2。实现过程描述：一开始第一组只包括顶点V1，第二组包括其他所有顶点。V1对应的距离值为0，第二组的顶点对应的距离值是这样确定的：若图中有弧V1，Vj，则Vj的距离为此弧的权值，否则Vj的距离为（或用一个很大的数表示）。然后每次从第二组的顶点中选一个其距离值为最小Vm的加入到第一组中，每往第一组中加入一个顶点Vm，就要对第二组中的各个顶点的距离值进行一次修正。若加进Vm做中间结点，使从V1到Vj的最短路径比不加Vm的路径要短，则要修改Vj的距离值。修改后再选距离值最小的顶点加入到第一组中。如此进行下去，直到图中所有顶点都包括在第一组中 ，或再也没有可加入到第一组中的顶点存在为止。4.2 Dijkstra算法对问题描述及实现：六个服务器节点S1、S2、S3、S4、S5和S6，分别如图表示，各个端点之间的权值标于节点间的联线之上。.G=(V,E)（1）此有加权图的邻接矩阵表示为：（2）对上述问题实现迪克斯屈拉算法的程序过程表述为：有邻接矩阵adjacent表示，若S1，Sj是图中的弧，则adjacent i，j的值等于边上所带的权值，否则adjacent i，j等于一个很大的正数infinity_value (在程序中用9999表示)。开始时adjacent i，j0表示顶点j未在第一组中，处理中用sj1标志第j个顶点已进入第一组。边的权值为adjacent对应的位置的值，数组元素的下标等于相关联顶点序号。数组distance_shortest n的每个元素为顶点的距离值，pre_node n的每个元素为从V1到该顶点的路径上此顶点的前一个顶点的序号，若从V1到该顶点无路径，则用0作为其前一个顶点序号。算法结束时，沿着顶点Vj对应的pre_node j1追溯，就能确定V1到Vj最短路径，其最短路径长度等于distance_shortest j1。此算法起始顶点也可以不是V1，起始顶点的序号由变量k给出（即从顶点Vk出发）。源点为Vk(其中k为1)（3）解决上述问题迪克斯屈拉程序源代码为：#include using namespace std;/定义常量#define maxnum 50/最大节点数目#define infinity_value 9999/无穷大值/定义数组，用于存放集合中的数据int distance_shortestmaxnum;/存放当前节点到达源节点的最短路径值int pre_nodemaxnum;/存放当前点的前一个节点int adjacentmaxnummaxnum;/邻接阵，存放边值int n;/节点个数/Dijkstra算法函数/n 节点个数 ，source 源节点void Dijkstra(int n,int source,int *distance_shortest,int *pre_node,int adjacentmaxnummaxnum)bool smaxnum;/定义存放点的集合/初始化for (int i=1;i=n;i+)distance_shortesti=adjacentsourcei;/赋值si=0;/将集合置为空if (distance_shortesti=infinity_value)pre_nodei=0;elsepre_nodei=1;ssource=1;/source加入集合distance_shortestsource=0;/初始值为0/开始迭代，迭代n-1次for (i=2;i=n;i+)int temp=infinity_value;int u=source;/找出还未使用的点j的到源的最小路径中distance_shortestj;for (int j=1;j=n;j+)if (sj=0)&(distance_shortestjtemp)u=j;/保存最小值的号temp=distance_shortestj;su=1;/加入最短路径的点/更新distance_shortestfor ( j=1;j=n;j+)if (sj=0)&(adjacentujinfinity_value)int newdist=distance_shortestu+adjacentuj;if (newdist=1; -i)if(i != 1)cout quei ;elsecout quei endl;void main()cout请输入图的节点的个数： n;int p, q, len,num; / 输入p, q两端点及其路径长度len，num为要统计的源端点/ 初始化adjacent为infinity_valuefor(int i=1; i=n; +i)for(int j=1; j=n; +j)adjacentij = infinity_value;/录入图的边权值cout请按规则依次输入n个节点相邻的边数！endl;cout例如：请输入端点号：1endl;cout 请输入另一个端点号：2endl;cout 请输入1号端点和2号端点之间边的权值：20endl;cout 如果录入结束请按0结束endl;int judge=1;while(judge) cout p;if (p=0)break;cout q ;if (q=0)break;cout请输入p号端点与qlen;if (q=0)break;adjacentqp=adjacentpq = len;/ 无向图for( i=1; i=n; +i)distance_shortesti = infinity_value;for( i=1; i=n; +i)for(int j=1; j=n; +j)printf(%8d, adjacentij);printf(n);coutnum;Dijkstra(n, num, distance_shortest, pre_node, adjacent);/ 最短路径长度for (i=1;i=n;i+)if (i!=num)cout num号源端点到i号端点的最短路径长度值: distance_shortesti;cout ，最短路径为: ; searchPath(pre_node,num, i);（4）根据迪克斯屈拉算法得到的程序运行最后结果为：图1.程序运行结果图图2.程序运行结果图（续）从上述实例中可以看出，Dijkstra算法是典型的最短路径路由算法，比较适用于求出图中一个特定顶点到其他各顶点的最短路。在实际应用中，需要求出任意两点之间的最短路，比如选路问题，各个城市之间最短的路线；网络中路由问题，选择最短时延路径等等。但是，也可以根据以上的例子看出，该算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。对于顶点数目比较少的图来说，迪克斯屈拉算法可以比较方便的得出最短路结果，但是，对于顶点数目比较多的比较复杂的图来说，运用这种算法将涉及大量的运算，需要反复重复以上的程序，增加运算的时间复杂度，并且遍历计算的节点很多，所以效率低。但是，迪克斯屈拉算法无疑仍是一种优秀的算法，可以很好的解决实际中的最短路径问题，并且可以和其他算法结合在一起完成更复杂的寻路过程。5、结束语在本文中列举的网络服务器之间寻找最短路径