通信网基础及应用课程设计Word格式.docx
《通信网基础及应用课程设计Word格式.docx》由会员分享，可在线阅读，更多相关《通信网基础及应用课程设计Word格式.docx（14页珍藏版）》请在冰点文库上搜索。
初始化。
令N={1}。
对于不在N中的每个节点v，设置D（v）=l（1，v）
（对于与1不直接相连的节点取为∞）。
第二步：
找到一个不在N中的使D（w）最小的节点w，并将w加进集N中去，然后计算下式，以修改不在N中的所有其他节点的D（v）：
D（v）=min[D（v），D（w）+l（w，v）]
重复第二步，直至全部节点包括在N中。
2.3Dijkstra算法的实现
我们利用图1中所示的网作为例子讨论Dijkstra算法，我们的目的是求出源节点到网中所有其他节点的最短路径。
在求解过程中，采取步进方式，建立一个以源节点1为根的最短路径树，直到包括最远的节点在内为止。
到第k步，计算出到离源节点最近的k个节点的最短路径。
这些路径定义为在集N内。
图1一个网络的例子
在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段。
要选择一个权值最小的弧段就必须把所有的点都扫描一遍，将这些要扫描的点按其所在边的权值进行顺序排列，这样即可大大提高算法的执行效率。
沈阳大学
课程设计说明书NO.3
2.4Dijkstra算法的基本原理
Dijkstra算法解决的是有向图中最短路径问题。
Dijstra算法的基础操作是边的拓展。
图2中示出了以源节点1为根的最短距离树。
它的产生过程是：
当一个节点加入集合N时，它就连接到已在N中的适当点。
每个节点下面圆圈内的数字代表在第n步该节点加入树结构。
由节点1的最短距离树可以得到节点1的路由选择表，如图3所示。
该表指明了到相应的目的的地节点所应选的下一节点。
同理，我们可以求得节点2,3，…，6的路由选择表。
图2节点1到其他节点的最短距离（a）
沈阳大学
课程设计说明书NO.4
目的节点下一节点
22
34
44
54
64
图3节点1到其他节点的最短距离（b）
2.4.1Dijkstra算法的基本过程
Dijkstra算法是最短路径算法中最典型的一种算法，求最短路径就是解决一个节点到其他节点之间的最短路径的问题。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表方式。
大概过程：
创建两个表，OPEN,CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1．访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2．从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3．遍历考察这个点的子节点。
求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4．重复第2和第3步,直到OPEN表为空，或找到目标点。
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
算法具体的形式包括：
确定起点的最短路径问题-即已知起始结点，求最短路径的问题。
课程设计说明书NO.5
确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。
在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。
全局最短路径问题-求图中所有的最短路径。
2.4.2Dijkstra算法的步骤
图4示出了求图1网中节点1到其他节点最短路径的过程。
在表中画圆圈的数字表示该步骤中D（w）的最小值。
这样，相应的节点w就加到N中，D（v）的值就按要求更改。
因此，在初始化后的第1步，距离最小D（4）=w，节点4就加进集合N中；
在第2步，D（5）=2，节点5加进N中；
如此不断继续下去。
第5步以后，所有的节点都在N中，算法终止。
步骤
N
D
（2）
D（3）
D（4）
D（5）
D（6）
初始
{1}
2
5
1
∞
{1,4}
4
①
{1,4,5}
3
②
{1,2,4,5}
{1,2,3,4,5}
③
{1,2,3,4,5,6}
④
图4算法的计算过程
3、设计过程与分析
3.1设计内容
根据我们平常在通信网基础的课程中所学的知识，使用Dijkstra算法，设计一个
课程设计说明书NO.6
用C语言程序编译的求最短路径的程序。
以下为用邻接矩阵表示的图的Dijkstra算法的源程序。
3.2设计程序
#include<
stdio.h>
#defineMAXVEX100
typedefcharVexType;
typedeffloatAdjType;
typedefstruct
{Vextypevexs[MAXVEX];
/*顶点信息*/
AdjTypearcs[MAXVEX][MAXVEX];
/*边信息*/
intn;
/*图的顶点个数*/
}
GraphMatrix;
GraphMatrixgraph;
typedefstruct{
VexTypevertex;
AdjTypelength;
/*最短路径长度*/
intprevex;
/*从v0到达vi（i=1,2,...n-1）的最短路径上vi的前趋顶点*/
课程设计说明书NO.7
}Path;
Pathdist[6];
/*n为图中顶点个数*/
#defineMAX1e+8
voidinit（GraphMatrix*pgraph,Pathdist[]）
{
inti;
dist[0].length=0;
dist[0].prevex=0;
dist[0].vertex=pgraph->
vexs[0];
pgraph->
arcs[0][0]=1;
/*表示顶点v0在集合U中*/
for（i=1;
i<
n;
i++）/*初始化集合V-U中顶点的距离值*/
{dist[i].length=pgraph->
arcs[0][i];
dist[i].vertex=pgraph->
vexs[i];
if（dist[i].length!
=MAX）
dist[i].prevex=0;
elsedist[i].pervex=-1;
voiddijlstra（GraphMatrixgraph,Pathdist[]）
{inti,j,minvex;
AdjTypemin;
init（&
graph,dist）;
/*初始化，此时集合U中只有顶点v0*/
graph.n;
i++）
{min=MAX;
minvex=0;
for（j=1;
j<
j++）
if（（graph.arcs[j][j]==0&
&
（dist[j].length<
min））/*在V-U中选出距离值最小顶点*/
{min=dist[j].length;
minvex=j;
if（minvex==0）break;
/*从v0没有路径可以通往集合V-U中的顶点*/
graph.arcs[minvex][minvex]=1;
/*集合V-U中路径最小的顶点为minvex*/
j<
j++）/*调整集合V-U中的顶点的最短路径*/
课程设计说明书NO.8
{if（graph.arcs[j][j]==1）continue;
if（dist[j].length>
dist[minvex].length+graph.arcs[minvex][j]）
{dist[j].length=dist[minvex].length+graph.arcs[minvex][j];
dist[j].prevex=minvex;
}
voidinitgraph（）
{
inti,j;
graph.n=6;
for（i=0;
i++）
for（j=0;
j++）
graph.arcs[i][j]=（i==j?
0:
MAX）;
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
课程设计说明书NO.9
intmain（）
initgraph（）;
dijkstra（graph,dist）;
printf（"
（%.0f%d）"
dist[i].length,dist[i].prevex）;
return0;
课程设计说明书NO.10
3.3设计结果分析
Dijkstra算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
上面部分的源程序为已知点的名称保存在intA[pointnum]中,点间的路径和权值保存在数组intB[pointnum][pointnum]中，其中两点间无路径用-1表示，求voidDijkstra（intB[][],intpointnum,intdepart,intdest），其中intdepart表示出发点的名称,intdest表示终点名称。
输出结果：
depart->
中间点1->
中间点2->
dest
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍。
根据设计结果我们可以知道，如果从某顶点出发（此点称为源点），经边到达另一
课程设计说明书NO.11
顶点（称为终点）的路径不止一条，而如何找到一条路径使沿此路径上各边的权值之和为最小就是我们研究的问题。
通过C语言的编程和运行，我们就可以方便的用Dijkstra
算法求出最短路径。
4、设计体会
通过这次的课程设计，让我对所学的书本上的知识得到了实际上的应用，这不仅
使我对知识的记忆更加牢固，还让我对有关通信网基础里的最短路径算法有了更深的了解，让我了解到，我们平常所学的知识不是死的，我们在日常中也可以用到。
通过这次的学习，让我对通信网基础这门课程更加感兴趣了。
在这期间，我们同学间互相帮助，互相讲解不会的地方，让我们真正在快乐中学习到了知识。
我想我们一定会抓住每一次这种学习的机会，更加努力！
5、参考文献
[1]王承恕.通信网基础.北京：
人民邮电出版社，2002
[2]周昕．数据通信与网络技术．北京：
清华大学出版社，2004
[3]唐宝民，《通信网技术基础》，人民邮电出版社,2005
[4]申普兵，《计算机网络与通信》，人民邮电出版社2007
[5]马进．通信网分析[M]．北京：
人民交通出版社，2003．140-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-130
[4]NewmanWM,SbroullRF.PrinciplesofInteractiveComputerGraphics[M].NewYork:
McGrawHill,1979.10：
10-25
[5]卜小明,龙全求.一种薄板弯曲问题的四边形位移单元[J].力学学报,1991,23
（1）:
53-60
（参考期刊杂志格式为:
作者.论文题目[J].期刊名,出版年,卷号（期号）:
页码）（期刊名前不写出版地）
[6]MastriAR.Neuropathyofdiabeticneurogenicbladder[J].AnnInternMed,1980,92
（2）:
316-318
[7]范立南,韩晓微,王忠石等.基于多结构元的噪声污染灰度图像边缘检测研究[J].武汉大学学报（工学版）,2003，49（3）:
45-49
[8]index.asp
（一般情况下不要用网址作为参考文献，如果用，最多1个）
注：
[M]表示参考的是书籍；
[J]表示参考的是学术期刊的论文；
如果参考会议论文集中的论文用[C]。
要求：
全部打印在A4纸（二本），各级标题四号宋体加粗，正文文字小四号宋体，程序五号timesnewroman，字数3000字以上,15页以上。
严禁抄袭，如有雷同者，均按不及格论处
本页不用打印
升级会员 