《迪克斯屈拉最短路径算法图论论文》由会员分享，可在线阅读，更多相关《迪克斯屈拉最短路径算法图论论文（9页珍藏版）》请在金锄头文库上搜索。
1、姓名：沈敬红 学院：通信学院 学号：s1401311091计算机网络中迪克斯屈拉最短路径算法的程序实现及应用沈敬红 S140131109重庆邮电大学通信与信息工程学院摘要：本文首先介绍了图论的发展历程，介绍了图论在实际问题中的应用。其次，介绍了图论中最短路径的问题及相关内容，介绍了计算机网络中服务器之间存在的最短路径问题。然后，介绍了迪克斯屈拉（Dijkstra）最短路径算法。最后，依据算法的思想，分别实现了 Dijkstra 算法在求解计算网络最短路径的应用程序。关键词：最短路径 服务器 Dijkstra 算法 程序Abstract in this paper, we firstly int
2、roduce 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,
3、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)是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论
4、曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉 1736 年的论着中，他所考虑的原始问题有很强的实际背景。图论的发展已有 200 多年的历史，它发源于 18 世纪普鲁士的柯尼斯堡。当地的居民想知道能否从任意一陆地出发，走遍联接该城的 7 座桥又回到原地? 其条件是每座桥都经过一次并且只经过一次。 （具体见“七桥问题” ）在加权连通图中，寻求最短路径的问题有其实际背景，例如在某一国家或地区，城市与城市之间都互相连通，从一个城市到达另一城市存在着多条路径，如何实现最短的路径完成两个城市之间的货物运输就是一个解决图论中实现最短路径的问题。同样，比如需要架设电网、通信网络以及其他
5、的有线网络，基于全网的考虑之下，点和点之间怎样架设一条最短的线路就是一个实际的最短路问题。按照图论的表述，在一个图中，两点之间的路径可能有很多条，且每条路径所经过的边数可能是不同的，如果是网络，每条路径的各边权数之和也可能是不同的，怎样找到一条顶点对顶点之间的各边权数之和为最小的路径问题称为最短路问题 1。本文提出了一个计算机网络中服务器之间最短路径的问题背景，并在迪克斯屈拉（Dijkstra）算法的基础上，实现算法在服务器之间寻求最短路径的程序设计。2、图论相关概念 1,2：无向图：每一条边都是无向边的图称为无向图。姓名：沈敬红 学院：通信学院 学号：s1401311092链：设 u 和 v
6、 是任意图 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=（a ij）为 G 的邻
7、接矩阵，其中 aij为图 G 中以 xi 为起点且以 yj 为终点的边的数目。边权矩阵：设 G 是 n 阶加权简单图，规定 D=（d ij） mn 是图的加权矩阵，即dij w（i，j） 。若结点 i 到结点 j 无边可连（在有向图中是方向不一致）时，取 dij。3、问题描述在现有的 Internet 中存在着大量的不同种类的服务器 7，这些服务器为用户提供不同种类的数据服务，在服务器与服务器之间存在着数据的交流。如果，我们将各个服务器看做是一个顶点，将服务器与服务器之间的链接看做是一条边，则服务器组成的网络就是一个无向连通图 9。在这个图上，服务器与服务器之间的链路上都存在着一定的时延，由于
8、网络环境的不同，每个边上的时延均不相同，有的只有几十毫秒，有的却达到上百毫秒，这些毫秒数就可以看做边的权值，如何选择最佳的路径使得服务器与服务器之间的数据交换所需时间最短的问题，就变成了求解在无向连通加权图中寻求最短路径的问题。如下图为网络服务器之间的拓扑图：（注：S1-S6 为网络服务器节点，权值为 10ms/每单位值）4、迪克斯屈拉（Dijkstra）算法实现4.1 Dijkstra 算法 1描述： 算法基本思想：一个顶点 V1 作为源点，求该顶点到其他各顶点的最短路径，迪克斯屈拉提出了一个按路径长度递增的顺序产生最短路径的方法。此方法的基本思想是：把图中所有结点分成两组，第一组包括已确定
9、最短路径的顶点，第二组包括尚未确定最短路径的顶点 ，按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中，直到从 V1 出发可以到达的所有顶点都已包括在第一组中。在这过程中，总保持从 V1 到第一组各顶点的最短路径都不大于从 V1 到第二组的任何顶点的最短路径长度。另外，每个顶点对应一个距离值，第一组的顶点对应的距离值就是从 V1 到此顶点的最短路径长度，第二组的顶点对应的姓名：沈敬红 学院：通信学院 学号：s1401311093距离值是从 V1 到此顶点的只包括第一组的顶点为中间顶点的最短路径长度 2。实现过程描述：一开始第一组只包括顶点 V1，第二组包括其他所有顶点。V 1 对应的距离值
10、为 0，第二组的顶点对应的距离值是这样确定的：若图中有弧V 1，V j ，则 Vj 的距离为此弧的权值，否则 Vj 的距离为（或用一个很大的数表示） 。然后每次从第二组的顶点中选一个其距离值为最小 Vm 的加入到第一组中，每往第一组中加入一个顶点 Vm，就要对第二组中的各个顶点的距离值进行一次修正。若加进 Vm 做中间结点，使从 V1 到 Vj 的最短路径比不加 Vm 的路径要短，则要修改 Vj 的距离值。修改后再选距离值最小的顶点加入到第一组中。如此进行下去，直到图中所有顶点都包括在第一组中 ，或再也没有可加入到第一组中的顶点存在为止。4.2 Dijkstra 算法对问题描述及实现：六个服务
11、器节点 S1、S2 、S3、S4、S5 和 S6，分别如图表示，各个端点之间的权值标于节点间的联线之上。.G=(V,E)（1）此有加权图的邻接矩阵表示为：（2）对上述问题实现迪克斯屈拉算法的程序过程表述为：有邻接矩阵 adjacent 表示，若S 1，S j是图中的弧，则 adjacent i，j的值等于边上所带的权值，否则 adjacent i，j等于一个很大的正数 infinity_value (在程序中用 9999 表示 )。开始时 adjacent i，j0 表示顶点 j 未在第一组中，处理中用 sj1 标志第 j 个顶点已进入第一组。边的权值为 adjacent对应的位置的值，数组元
12、素的下标等于相关联顶点序号。数组 distance_shortest n的每个元素为顶点的距离值，pre_node n的每个元素为从 V1 到该顶点的路径上此顶点的前一个顶点的序号，若从 V1 到该顶点无路径，则用 0 作为其前一个顶点序号。算法结束时，沿着顶点 Vj 对应的 pre_node j1追溯，就能确定 V1 到 Vj 最短路径，其最短路径长度等于distance_shortest j1。此算法起始顶点也可以不是 V1，起始顶点的序号由变量 k 给出姓名：沈敬红 学院：通信学院 学号：s1401311094（即从顶点 Vk 出发） 。源点为 Vk(其中 k 为 1)（3）解决上述问题
13、迪克斯屈拉程序源代码为：#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,i
14、nt source,int *distance_shortest,int *pre_node,int adjacentmaxnummaxnum)bool smaxnum;/定义存放点的集合/初始化for (int i=1;i=1; -i)if(i != 1)姓名：沈敬红 学院：通信学院 学号：s1401311096cout ;elsecout n;int p, q, len,num; / 输入 p, q 两端点及其路径长度 len，num 为要统计的源端点/ 初始化 adjacent为 infinity_valuefor(int i=1; i p;if (p=0)break;cout q ;i
15、f (q=0)break;coutlen;if (q=0)break;adjacentqp=adjacentpq = len;/ 无向图for( i=1; inum;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）根据迪克斯屈拉算法得到的程序运行最后结果为：姓名：沈敬红 学院：通信学院 学号：s1401311098图 1.程序运行结果图图 2.程序运行结果图（续）姓名：沈敬红 学院：通信学院 学号：s1401311099从上述实例中可以看出，Dijkstra 算法是典型的最短路径路由算法，比较适用于求出图中一个特定顶点到其他各顶点的最短路。在实际应用中，需要求出任意两点之间的最短路，比如选路问题，各个城市之间最短的
