资源描述：
《课程设计改_图文文库》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于Dijstra最短路径算法1•课程设计的目的为了巩固“数据通信与通信网技术”课程学到的相关知识，通过对本课程所学知识的综合运用，使学生融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和扩频通信系统等相关知识；加深对通信网络的基木理论、基木知识和常用技术的理解；提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力。2.设计方案论证问题描述给定一个带权无向图G二(V,E),其中每条边的权是一个非负实数。另外，还给定V屮的一个项点，称为源。现在我们要计算从源到所有其他各项点的最短路径长度。这里的长度是指
2、路上各边权Z和，这个问题通常称为单源最短路径问题。最短路径最短路径问题是图论研究中的一个经典算法问题，在日常生活中，我们如果需耍常常往返A地区和B地区Z间，我们最希望知道的可能是从A地区到B地区间的众多路径屮，那一条路径的路途最短。最短路径问题是图论研究屮的一个经典算法问题，旨在寻找图(由结点和路径组成的)屮两结点Z间的最短路径。算法具体的形式包括：1•确定起点的最短路径问题-即已知起始结点，求最短路径的问题。2•确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图屮该问题与
3、确定起点的问题完全等同，在有向图屮该问题等同于把所有路径方向反转的确定起点的问题。3•确定起点终点的最短路径问题-即己知起点和终点，求两结点之间的最短路径。4.全局最短路径问题-求图中所有的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。算法介绍辿杰斯特拉算法是由荷兰计算机科学家狄克斯特拉丁1959年捉出的，因此又叫狄克斯特拉算法是从一个顶点到其余齐顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法原理1
4、•首先，引入一个辅助向量D,它的每个分量D[i]表示当前所找到的从起始点V(即源点V)到其它每个顶点Vi的长度。例如，D[3]=2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程屮D的值是在不断逼近最终结果但在过程屮不一定就等于长度。2.D的初始状态为：若从V到Vi有弧(即从V到Vi存在连接边)，则D[i]为弧上的权值(即为从V到Vi的边的权值)；否则置D为8。显然，长度为D[i]=Min{D
5、ev}的路径就是从V出发到顶点Vj的长度最短的一条路径，此路径为(V,Vj)o3•那么，下一条长
6、度次短的是哪一条呢？也就是找到从源点V到下一个顶点的最短路径氏度所对应的顶点，且这条最短路径长度仅次于从源点V到顶点Vj的最短路径长度。假设该次短路径的终点是Vk,则可想而知，这条路径要么是(V,Vk),或者是(V,Vj,Vk)o它的长度或者是从V到Vk的弧上的权值，或者是D[j]加上从Vj到Vk的弧上的权值。4•一般情况下，假设S为已求得的从源点V出发的最短路径长度的顶点的集合,则可证明：下一条次最短路径(设其终点为X)要么是弧(V,X),或者是从源点V出发的中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条
7、长度次短的的最短路径长度必是D[]]=Min{D
8、GV-S},K中D[i]要么是弧(V,Vi)上的权值，或者是D[kl(VkeS)和弧(Vk,Vi)上的权值之和。算法思想按路径长度递增次序产生算法把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合将T屮顶点按递增的次序加入到S屮，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的长度T屮顶点：从V0到此顶点的只包括S屮顶
9、点作屮间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值Z和（反证法可证）求最短路径步骤算法步骤如下：G二{V,E}1.初始时令S={VO},T=V-S={其余顶点},T屮顶点对应的距离值若存在,d（VO,Vi）为〈VO,Vi>弧上的权值若不存在,d（VO,Vi）为82.从T中选取一个与S中顶点有关联边且权值最小的顶点W,加入到S中3.对其余T屮顶点的距离值进行修改：若加进W作屮间顶点，从V0到Vi的距离值缩短，则
10、修改此距离值3设计的过程与分析问题算法设G=（V,E）是一个带权有向图，把图中顶点集合V、分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二（2）从
