通信网基础及应用课程设计.doc

课程设计说明书 NO.1C语言环境下D算法完成最短路径求解1.课程设计的目的为了巩固“通信网基础及应用”课程学到的相关知识，通过对本课程所学知识的综合运用，使学生融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和扩频通信系统等相关知识；加深对通信网络的基本理论、基本知识和常用技术的理解；提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力。2.设计方案论证2.1最短路径算法的分类用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。 最常用的路径算法有： 1.Dijkstra算法,是解决一个节点到其他节点之间的最短路径的问题。2.A*算法。3.SPFA算法。4.Bellman-Ford算法。5.Floyd-Warshall算法，可以用来求解网中任意两个节点之间的最短路径。6.Johnson算法。所谓单源最短路径问题是指：已知G（V，E），我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。 首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。2.2经典Dijkstra算法的主要思想Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最 沈 阳 大 学课程设计说明书 NO2短路径算法的基本过程如下：第一步：初始化。令N=1。对于不在N中的每个节点v，设置D（v）=l（1，v）（对于与1不直接相连的节点取为）。 第二步：找到一个不在N中的使D（w）最小的节点w，并将w加进集N中去，然后计算下式，以修改不在N中的所有其他节点的D（v）： D（v）=minD（v），D（w）+l（w，v） 重复第二步，直至全部节点包括在N中。2.3 Dijkstra算法的实现我们利用图1中所示的网作为例子讨论Dijkstra算法，我们的目的是求出源节点到网中所有其他节点的最短路径。在求解过程中，采取步进方式，建立一个以源节点1为根的最短路径树，直到包括最远的节点在内为止。到第k步，计算出到离源节点最近的k个节点的最短路径。这些路径定义为在集N内。图1一个网络的例子在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段。要选择一个权值最小的弧段就必须把所有的点都扫描一遍，将这些要扫描的点按其所在边的权值进行顺序排列，这样即可大大提高算法的执行效率。 沈 阳 大 学课程设计说明书 NO.32.4 Dijkstra算法的基本原理Dijkstra算法解决的是有向图中最短路径问题。Dijstra算法的基础操作是边的拓展。图2中示出了以源节点1为根的最短距离树。它的产生过程是：当一个节点加入集合N时，它就连接到已在N中的适当点。每个节点下面圆圈内的数字代表在第n步该节点加入树结构。由节点1的最短距离树可以得到节点1的路由选择表，如图3所示。该表指明了到相应的目的的地节点所应选的下一节点。同理，我们可以求得节点2,3，6的路由选择表。图2 节点1到其他节点的最短距离（a） 沈 阳 大 学课程设计说明书 NO.4 目的节点 下一节点2 23 44 45 46 4图3 节点1到其他节点的最短距离（b）2.4.1 Dijkstra算法的基本过程Dijkstra算法是最短路径算法中最典型的一种算法，求最短路径就是解决一个节点到其他节点之间的最短路径的问题。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式。大概过程： 创建两个表，OPEN, CLOSE。 OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 1 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。 2 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。 3 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。 4 重复第2和第3步,直到OPEN表为空，或找到目标点。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。 沈 阳 大 学课程设计说明书 NO.5确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题 - 求图中所有的最短路径。2.4.2 Dijkstra算法的步骤图4示出了求图1网中节点1到其他节点最短路径的过程。在表中画圆圈的数字表示该步骤中D（w）的最小值。这样，相应的节点w就加到N中，D（v）的值就按要求更改。因此，在初始化后的第1步，距离最小D（4）=w，节点4就加进集合N中；在第2步，D（5）=2，节点5加进N中；如此不断继续下去。第5步以后，所有的节点都在N中，算法终止。步骤ND（2）D（3）D（4）D（5）D（6）初始125111,424221,4,5231431,2,4,5312441,2,3,4,5212451,2,3,4,5,62312图4 算法的计算过程3、设计过程与分析3.1设计内容 根据我们平常在通信网基础的课程中所学的知识，使用Dijkstra算法，设计一个 沈 阳 大 学课程设计说明书 NO.6用C语言程序编译的求最短路径的程序。以下为用邻接矩阵表示的图的Dijkstra算法的源程序。3.2设计程序#include<stdio.h>#define MAXVEX 100typedef char VexType;typedef float AdjType;typedef structVextype vexsMAXVEX;/*顶点信息*/AdjType arcsMAXVEXMAXVEX;/*边信息*/int n;/*图的顶点个数*/GraphMatrix;GraphMatrix graph;typedef structVexType vertex;/*顶点信息*/AdjType length;/*最短路径长度*/int prevex;/*从v0到达vi(i=1,2,.n-1)的最短路径上vi的前趋顶点*/ 沈 阳 大 学课程设计说明书 NO.7Path;Path dist6;/*n为图中顶点个数*/#define MAX 1e+8void init(GraphMatrix* pgraph,Path dist)int i;dist0.length=0;dist0.prevex=0;dist0.vertex=pgraph->vexs0;pgraph->arcs00=1;/*表示顶点v0在集合U中*/for(i=1;i<pgraph->n;i+)/*初始化集合V-U中顶点的距离值*/disti.length=pgraph->arcs0i;disti.vertex=pgraph->vexsi;if(disti.length!=MAX)disti.prevex=0;else disti.pervex=-1;void dijlstra(GraphMatrix graph,Path dist)int i,j,minvex;AdjType min;init(&graph,dist);/*初始化，此时集合U中只有顶点v0*/for(i=1;i<graph.n;i+)min=MAX;minvex=0;for(j=1;j<graph.n;j+)if(graph.arcsjj=0&&(distj.length<min)/*在V-U中选出距离值最小顶点*/min=distj.length;minvex=j;if(minvex=0) break; /* 从v0没有路径可以通往集合V-U中的顶点 */ graph.arcsminvexminvex=1; /* 集合V-U中路径最小的顶点为minvex */ for(j=1; j<graph.n; j+) /* 调整集合V-U中的顶点的最短路径 */ 沈 阳 大 学课程设计说明书 NO.8 if(graph.arcsjj=1) continue; if(distj.length>distminvex.length+graph.arcsminvexj) distj.length=distminvex.length+graph.arcsminvexj; distj.prevex=minvex; void initgraph() int i,j; graph.n=6; for(i=0;i<graph.n;i+) for(j=0;j<graph.n;j+) graph.arcsij=(i=j?0:MAX); graph.arcs01=50; graph.arcs02=10; graph.arcs12=15; graph.arcs14=5; graph.arcs20=20; graph.arcs23=15; graph.arcs31=20; graph.arcs34=35; graph.arcs43=30; graph.arcs53=3; graph.arcs04=45; 沈 阳 大 学课程设计说明书 NO.9int main() int i; initgraph(); dijkstra(graph,dist); for(i=0;i<graph.n;i+) printf("(%.0f %d)",disti.length,disti.prevex); return 0; void initgraph() int i,j; graph.n=6; for(i=0;i<graph.n;i+) for(j=0;j<graph.n;j+) graph.arcsij=(i=j?0:MAX); graph.arcs01=50; graph.arcs02=10; graph.arcs12=15; graph.arcs14=5; graph.arcs20=20; graph.arcs23=15;graph.arcs31=20; graph.arcs34=35; 沈 阳 大 学课程设计说明书 NO.10graph.arcs43=30; graph.arcs53=3; graph.arcs04=45; int main() int i; initgraph(); dijkstra(graph,dist); for(i=0;i<graph.n;i+) printf("(%.0f %d)",disti.length,disti.prevex); return 0;3.3设计结果分析Dijkstra算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 上面部分的源程序为已知点的名称保存在int Apointnum中,点间的路径和权值保存在数组int Bpointnumpointnum中，其中两点间无路径用-1表示，求void Dijkstra(int B,int pointnum,int depart,int dest)，其中int depart表示出发点的名称,int dest表示终点名称。输出结果：depart->中间点1->中间点2->destDijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍。根据设计结果我们可以知道，如果从某顶点出发（此点称为源点），经边到达另一 沈 阳 大 学课程设计说明书 NO.11顶点（称为终点）的路径不止一条，而如何找到一条路径使沿此路径上各边的权值之和为最小就是我们研究的问题。通过C语言的编程和运行，我们就可以方便的用Dijkstra算法求出最短路径。4、设计体会 通过这次的课程设计，让我对所学的书本上的知识得到了实际上的应用，这不仅使我对知识的记忆更加牢固，还让我对有关通信网基础里的最短路径算法有了更深的了解，让我了解到，我们平常所学的知识不是死的，我们在日常中也可以用到。通过这次的学习，让我对通信网基础这门课程更加感兴趣了。在这期间，我们同学间互相帮助，互相讲解不会的地方，让我们真正在快乐中学习到了知识。我想我们一定会抓住每一次这种学习的机会，更加努力！5、参考文献1王承恕 . 通信网基础.北京：人民邮电出版社，20022周昕数据通信与网络技术北京：清华大学出版社，20043唐宝民，通信网技术基础，人民邮电出版社,20054申普兵，计算机网络与通信，人民邮电出版社20075马进通信网分析M北京：人民交通出版社，2003140-180，193-218 沈 阳 大 学课程设计说明书 NO.12 沈 阳 大 学课程设计说明书 NO.13 沈 阳 大 学课程设计说明书 NO.14 沈 阳 大 学课程设计说明书 NO.15 沈 阳 大 学参考文献要列出3篇以上，格式如下：1谢宋和,甘 勇.单片机模糊控制系统设计与应用实例M.北京:电子工业出版社, 1999.5：20-25（参考书或专著格式为:著者.书名M.版本(第1版不注).出版地:出版者,出版年月：引文所在页码）2潘新民,王燕芳.微型计算机控制技术M,第2版.北京:电子工业出版社, 2003.4：305-350（1本书只能作为1篇参考文献，不能将1本书列为多个参考文献）3范立南,谢子殿.单片机原理及应用教程M.北京:北京大学出版社, 2006.1：123-1304 Newman W M, Sbroull R F. Principles of Interactive Computer GraphicsM. New York: McGraw Hill, 1979.10：10-255卜小明,龙全求.一种薄板弯曲问题的四边形位移单元J.力学学报, 1991,23(1):53-60（参考期刊杂志格式为:作者.论文题目J.期刊名,出版年,卷号(期号):页码）（期刊名前不写出版地）6Mastri A R. Neuropathy of diabetic neurogenic bladderJ. Ann Intern Med, 1980, 92(2):316-3187范立南,韩晓微,王忠石等.基于多结构元的噪声污染灰度图像边缘检测研究J.武汉大学学报(工学版), 2003，49(3):45-498 index.asp（一般情况下不要用网址作为参考文献，如果用，最多1个）注：M表示参考的是书籍；J表示参考的是学术期刊的论文；如果参考会议论文集中的论文用C。 要求：全部打印在A4纸（二本），各级标题四号宋体加粗，正文文字小四号宋体，程序五号times new roman，字数3000字以上,15页以上。严禁抄袭，如有雷同者，均按不及格论处注：本页不用打印