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

《通信网基础及应用课程设计new》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计说明书NO.1C语言环境下D算法完成最短路径求解1.课程设计的目的为了巩固“通信网基础及应用”课程学到的相关知识，通过对本课程所学知识的综合运用，使学生融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和扩频通信系统等相关知识；加深对通信网络的基本理论、基本知识和常用技术的理解；提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力。2.设计方案论证2.1最短路径算法的分类用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：　　1.Dijkstra算法,是解决一个节点到其他节点之间的最短路径的问

2、题。　　2.A*算法。　　3.SPFA算法。　　4.Bellman-Ford算法。　　5.Floyd-Warshall算法，可以用来求解网中任意两个节点之间的最短路径。　　6.Johnson算法。　　所谓单源最短路径问题是指：已知G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。2.2经典Dijkstra算法的主要思想Dijkstra算法的基本思路是：假设每个点都有一对标号(dj,pj)，其中d

3、j是从起源点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）=min[D（v），D（w）+l（w，v）]重复第二步，直至全部节点包括在N中。2.3Dijk

4、stra算法的实现我们利用图1中所示的网作为例子讨论Dijkstra算法，我们的目的是求出源节点到网中所有其他节点的最短路径。在求解过程中，采取步进方式，建立一个以源节点1为根的最短路径树，直到包括最远的节点在内为止。到第k步，计算出到离源节点最近的k个节点的最短路径。这些路径定义为在集N内。图1一个网络的例子在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段。要选择一个权值最小的弧段就必须把所有的点都扫描一遍，将这些要扫描的点按其所在边的权值进行顺序排列，这样即可大大提高算法的执行效率。沈阳大学课程设计说明书NO.

5、32.4Dijkstra算法的基本原理Dijkstra算法解决的是有向图中最短路径问题。Dijstra算法的基础操作是边的拓展。图2中示出了以源节点1为根的最短距离树。它的产生过程是：当一个节点加入集合N时，它就连接到已在N中的适当点。每个节点下面圆圈内的数字代表在第n步该节点加入树结构。由节点1的最短距离树可以得到节点1的路由选择表，如图3所示。该表指明了到相应的目的的地节点所应选的下一节点。同理，我们可以求得节点2,3，…，6的路由选择表。图2节点1到其他节点的最短距离（a）沈阳大学课程设计说明书NO.4目的节点下一节点2234445464图3节点1到其

6、他节点的最短距离（b）2.4.1Dijkstra算法的基本过程Dijkstra算法是最短路径算法中最典型的一种算法，求最短路径就是解决一个节点到其他节点之间的最短路径的问题。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表方式。大概过程：　　创建两个表，OPEN,CLOSE。　　OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。　　1．访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。　　2．从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这

7、个点放到CLOSE表中。　　3．遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。4．重复第2和第3步,直到OPEN表为空，或找到目标点。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题-即已知起始结点，求最短路径的问题。沈阳大学课程设计说明书NO.5确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。　

8、　确定起点终点的最短路径问题-即已知起点和终点，求两