课程设计改_图文文库

1、基于dijstra最短路径算法1课程设计的目的为了巩固“数据通信与通信网技术”课程学到的相关知识，通过对本课程所学知识 的综合运用，使学生融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和 扩频通信系统等相关知识；加深对通信网络的基木理论、基木知识和常用技术的理解； 提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力。2.设计方案论证问题描述给定一个带权无向图g二(v,e),其中每条边的权是一个非负实数。另外，还给定v 屮的一个项点，称为源。现在我们要计算从源到所有其他各项点的最短路径长度。这里 的长度是指路上各边权z和，这个问题通常称为单源最短路径问题。最短路径最短路径问题

2、是图论研究中的一个经典算法问题，在日常生活中，我们如果需耍 常常往返a地区和b地区z间，我们最希望知道的可能是从a地区到b地区间的众多路 径屮，那一条路径的路途最短。最短路径问题是图论研究屮的一个经典算法问题，旨在 寻找图(由结点和路径组成的)屮两结点z间的最短路径。算法具体的形式包括：1 确定起点的最短路径问题-即已知起始结点，求最短路径的问题。2确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点， 求最短路径的问题。在无向图屮该问题与确定起点的问题完全等同，在有向图屮该问题 等同于把所有路径方向反转的确定起点的问题。3确定起点终点的最短路径问题-即己知起点和终点，求两结点之

3、间的最短路 径。4.全局最短路径问题-求图中所有的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算 法”。算法介绍辿杰斯特拉算法是由荷兰计算机科学家狄克斯特拉丁 1959年捉出的，因此又叫狄 克斯特拉算法是从一个顶点到其余齐顶点的最短路径算法，解决的是有向图中最短路 径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为 止。算法原理1首先，引入一个辅助向量d,它的每个分量d i表示当前所找到的从起始点 v (即源点v)到其它每个顶点vi的长度。例如，d3 = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就 是说在算法执行过程

4、屮d的值是在不断逼近最终结果但在过程屮不一定就等于长度。2. d的初始状态为：若从v到vi有弧(即从v到vi存在连接边)，则di为弧 上的权值(即为从v到vi的边的权值)；否则置d 为8。显然，长度为di=min d|ev 的路径就是从v出发到顶点vj的长度最短的一 条路径，此路径为(v, vj)o3那么，下一条长度次短的是哪一条呢？也就是找到从源点v到下一个顶点的 最短路径氏度所对应的顶点，且这条最短路径长度仅次于从源点v到顶点vj的最短路 径长度。假设该次短路径的终点是vk,则可想而知，这条路径要么是(v, vk),或者是 (v, vj, vk)o它的长度或者是从v到vk的弧上的权值，或者

5、是dj加上从vj到vk 的弧上的权值。4一般情况下，假设s为已求得的从源点v出发的最短路径长度的顶点的集合, 则可证明：下一条次最短路径(设其终点为x)要么是弧(v, x),或者是从源点v出 发的中间只经过s中的顶点而最后到达顶点x的路径。因此，下一条长度次短的的最短路径长度必是d = min d|gv-s , k中di要 么是弧(v, vi)上的权值，或者是dkl(vkes)和弧(vk,vi)上的权值之和。算法思想按路径长度递增次序产生算法把顶点集合v分成两组：（1）s：已求出的顶点的集合（初始时只含有源点v0）（2）v-s=t：尚未确定的顶点集合将t屮顶点按递增的次序加入到s屮，保证：（1

6、）从源点v0到s中其他各顶点的长度都不大于从v0到t中任何顶点的最短 路径长度（2）每个顶点对应一个距离值s中顶点：从v0到此顶点的长度t屮顶点：从v0到此顶点的只包括s屮顶点作屮间顶点的最短路径长度依据：可以证明v0到t中顶点vk的，或是从v0到vk的直接路径的权值；或 是从v0经s中顶点到vk的路径权值z和（反证法可证）求最短路径步骤算法步骤如下：g二v, e1.初始时令s=vo,t=v-s=其余顶点, t屮顶点对应的距离值若存在 <vo,vi>, d（vo,vi）为vo,vi>弧上的权值若不存在<vo,vi>, d（vo,vi）为82. 从t中选取一个与s中

7、顶点有关联边且权值最小的顶点w,加入到s中3. 对其余t屮顶点的距离值进行修改：若加进w作屮间顶点，从v0到vi的距 离值缩短，则修改此距离值3设计的过程与分析问题算法设g= （v, e）是一个带权有向图，把图中顶点集合v、分成两组，第一组为已求出最 短路径的顶点集合（用s表示，初始时s中只有一个源点，以后每求得一条最短路径，就 将加入到集合s中，直到全部顶点都加入到s中，算法就结束了），第二组为其余未确 定最短路径的顶点集合（用u表示），按最短路径长度的递增次序依次把第二（2）从u中选取一个距离v最小的顶点k,把k,加入s屮（该选定的距离就 是v到k的最短路径长度）。（3）以k为新考虑的中间

8、点，修改u中各顶点的距离；若从源点v到顶点u（u u）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修 改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所冇顶点都包含在s屮。表1算法的计算过程节点12345610332002302103320200421001450021056000450表1示岀了图1网中节点1到其他节点最短路径的过程。在表中画圈的数字表示 该步骤屮d（v）的最小值。这样，相应的节点w就加到n屮，d （v）的值就按耍求更改。 将下面中的程序导入软件中，调试程序，把输出的结果截屏。#define max_vertex_num 1

9、00最大顶点数#include <stdio.h>#include <stdlib.h>#define maxjnt 10000无穷大typedef int adjtype;typedef struct int pi m ax_vertex_num;存放v到vi的一条最矩路径int end;pathtype;typedef char vtype;设顶点为字符类型typedef structvtype vmax_vertex_num;顶点存储空间adjtypeamax_vertex_numjlmax_vertex_numj;邻接矩阵mgraph;邻接矩阵表示的图/floy

10、d 算法求网g (用邻接矩阵表示)中任意两点间最短路径/d川是最短路径长度矩阵，path最短路径标志矩阵void floyd(mgraph * g,int pathmax_vertex_num,int dmax_vertex_num,int n) int i,j,k;for(i=0;i<n;i+)初始化for(j=0;j<n;j+)if(g->aij<maxnt) pathij=j;elsepathij=-l;diju=g->aij;for(k=0;k<n;k+)进行n次试探for(i=0;i<n;i+)for(j=0;j<n;j+)if(dij

11、>dik+dkj)diju=dik+dkuj;取小者pathiu=pathik;改vi的后继)int main()int i j,k,v=0,n=6;v为起点，n为顶点个数mgraph g;int pathmax_vertex_nummax_vertex_num;v到各顶点的最短路径向量intdmax_vertex_nummax_vertex_num;/v到各顶点最短路径长度向量/初始化adjtype amax_vertex_nummax_vertex_num= 0,3,3,2,maxn t,max_int,3,0,2,1 ,max_int,max_int,3,2,o,2,max_1nt

12、,max_int,2,1, max_int,0,1,4,max_int,maxn t,2,1,0,5,max_int,max_int,maxn t,4,5,0；for(i=0;i<n;i+)for(j=0;j<n;j+)gaiju=aij;floyd( &gpath,d,6);for(i=0;i<n;i+)/输出每对顶点间最短路径长度及最短路径 for(j=0;j<n;j 卄)printf(nv%d 到 v%d 的最短长度:”,i,j); printf(”df,di|j);输出vi到vj的最短路径长度 k=pathij;/jr路径上 vi 的后续 vk if(k

13、=-i)printf("there is no path between v%d and v%dn”,i,j);路径不存在else printf("最短路径为:”);printf(”(v%d”,i);输出vi的序号iwhile(k!=j)k不等于路径终点j时printf(,v%d,k);输出kk=pathkfj;求路径上下一顶点序号)printf(“,v%d)n”,j);输出路径终点序号printf(,n,r);)system(mpause");return 0;)通过对该算法的仔细分析与研究可以得出，上述算法屮有几点不足之处：(1) 用邻接矩阵cost来存储网络

14、图，其存储量为n*n。对于大型稀疏矩阵，这将耗费 大量资源存储那些无意义的矩阵元素。(2) 当从未标记节点集合(v-s)选定下一个节点vj作中间节点后，在更新操作过程 中，需要扫描所有的未标记节点并进行比较更新。而未标记节点集合(v-s) -1 往往包含大量与屮间节点vj不直接相连的节点。(3) 在选择下一个最短路径节点作为中间节点时，需要比较所有的未标记节点，而 这个屮间节点往往包含在与已标记节点s集合的所冇节点邻接的节点屮。(4) 在算法的每次迭代中，由于未标记节点以无序的形式存放在一个链表中或一个 数组中，每次选择最短路径节点都必须将所有未标记节点扫描一遍，当节点数目很大时, 这无疑将成

15、为制约计算速度的关键因素。dijkstra算法用于计算一个源节点到所有其他节点的最短代价路径，它是按路 径长度递增的次序来产生最短路径的算法。假设用带权的邻接矩阵cost来表示具有n 个结点的带权有向图g3,costi, j表示弧vi,vj的权值，如果从vi到vj不通，则 costi, j二。引进一个辅助向量dist并设vs为起始点，每个分量disti表示已找到的 从起始点vs到每个终点vi的最小权值。则该向量的初始值为:disti=costs, ivi!vo 其屮，v是结点的集合。令s为经找的从起点出发的最短路径的终点集合，初始值为 s=vs，则从vs出发到图g上其它所有结点vi可能达到的最

16、短路径长度为 disti二costs, ivi!v。(1) 选择vj,使得dj=mindi|vi!v-so vj就是当前求得的一条从vs出发的 最短路径的终点，令s=svvjo(2) 修改从vs到集合v-s中任意一顶点vk的最短路径长度。如果 dj+costj, k<dk,则进行第(3)步。(3) 修改 di st k为 di sk k二di st j +cost j, k;重复第 2、3 步操作共 n-l 次,由 此求得从vs到其他顶点的最优路径，该路径是各权值递增的序列。改进的dijkstra算法基本思想设置两个集合s和adj及一个数组t, s是已标记集合,adj是邻接点集,t存储

17、待排序节点。初始状态时,s= vo,t=adjvo,首先,将数组t通过堆排序调整为小顶堆，取 数组首元即堆顶节点current为屮间节点，并将current加入到已标记集合s屮；再次, 比较更新current的邻接点集合与已标记集合的差集(adj current-s)中任一节点vi 的当前最短路径值。然后杳找s集合所有节点的邻接点的并集与s集合的差集(vadjs)-s),同时将 这些节点顺次存入数组t中,覆盖原数组中的节点，并设置一个计数器i记录节点个数; 最后将数组屮的前i个元素按它们当前的最短路径值调整成小顶堆，取堆顶节点为下一 个最短路径节点将其归并到集合s中。如此反复迭代循环,直到所有

18、的节点都加入到集 合s屮。传统dijkstra算法使用的是邻接矩阵來存储网络图，存储量为n*n,而使用邻接表 來存储网络数据信息，可使存储空间减少至n量级。另外，利用堆排序来选择最短路径节 点，只处理标记节点的相邻节点，从而大量减少了要计算的节点数，最终使得算法的吋间 复杂度由原来的0(n2)降至0(n(logn+e)。随着网络中节点数目和边数的增多，这种改 进的dijkstra算法越来越显示出英优势，可使算法所需的时间明显减少,并获得精度较 高的结杲。岬u啲最短长度：3最翹路径为：（u4,u2,u0”鈿i的最短长度：2最翹路径为：（u4,u2,ui114鈿2的最翹长度：0最癒路径为：0>

19、;4,u2）”鈿3的最更长度：2最短路径为：（u4,u3）”到u啲最馬长度最更路径为：（u4,u4”硼的最啟度：0最短路径为讹45）”5鈿0的最短长度：6最更路径为电530翊u1的最就度：5最更路径划临忆吐*鈿2的最短长度：5最更路径为农542*鈿啲最短长度：4最翹路径为讹53”鈿4的最短长度：5ftg 路径为：u5,u4)”鈿5的最翹长度：0最想路径为：0>5,u5詁任意魁续图4结果图4.设计体会通过这次课程设计，让我更加深刻了解课本知识，和以往对知识的疏忽得以补充, 设计过程中遇到一些模糊的公式和专业用语，比如说floyd算法、最小生成树。在使用 参考书时，有的数据很难查出，但是这些

20、问题经过这次课程设计，都一一得以解决，我 相信这木书屮还有很多我为搞清楚的问题，但是这次的课程设计给我相当的基础知识， 为我以后工作打下了严实的基础。虽然这次课程是那么短暂的1周时间，我感觉到这些天我的所学胜过我这一学期 所学，这次任务原则上是设计，其实就是一次大的作业。在整个的制作过程中，编写程 序和了解算法原理是最困难的，出于对这些得不熟悉，花费了很多得时间，通过询问老 师，同学和去图书馆查询，终于找到了解决的办法。通信网基础是通信的专业课。学好 这门课程对我们在以后得通信学习有着很大得帮助。在我遇到困难的时候，是吴老师和 同学帮助了我，我很感谢他们。通过这次课程设计发现这其中需要的很多知

21、识我们没有接触过，去图书馆杳资料 的吋候发现我们前边所学到的仅仅是皮毛，还冇很多需要我们掌握的东西我们根本不知 道。同吋也发现有很多已经学过的东西我们没有理解到位，不能灵活运用于实际，不能 很好的用来解决问题，这就需要我们不断的大量的实践，通过不断的口学，不断地 发现问题，思考问题，进而解决问题。在这个过程屮我们将深刻理解所学知识，同时也 可以学到不少很实用的东西。，同时让我对课木知识的巩固和对基木公式的熟悉和应用, 及熟练使用dijkstra算法用c语言软件进行计算。使我做事的耐心和仔细程度得以提 高。课程设计是培训学生运用木专业所学的理论知识和专业知识来分析解决实际问题的 重要教学环节，是

22、对本学年所学知识的复习和巩固。同样，也促使了同学们的相互探讨, 相互学习。因此，我们必须认真、谨慎、踏实、一步一步的完成设计。如果时间可以重 來，我可能会认真的去学习和研究，也可能会门己独立的完成一个项目，我相信无论是 谁看到自己做出的成果时心里一定会很兴奋。此次设计让我明片了一个很深刻的道理： 团队精神固然很重要，担人往往还是要靠自己的努力，自己亲身去经历，这样自己的心 里才会踏实，学到的东西才会更多。课程设计是一个重妾的教学环节，通过课程设计使 我们了解到一些实际与理论z间的差异。通过课程设计不仅可以巩固专业知识，为以后 的工作打下了坚实的基础，而其还可以培养和熟练使用资料，运用工具书的能

23、力，把我 们所学的课本知识与实践结合起來，起到温故而知新的作用。课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同吋， 设计让我感触很深。使我对抽彖的理论有了具体的认识。在课程设计过程中。以设计 任务书的指导思想为屮心，参照冇关资料，冇计划冇头绪、冇逻辑地把这次设计搞好! 总z,这次课程设计使我收获很多、学会很多、比以往更有耐心很多。感谢学校及老师 给我们这次课程设计的机会，最真挚的感谢我们的辅导老师，在设计过程中，老师精心 的辅导和不厌英烦地的态度才使得我们以顺利的完成这次设计，同时也增加我们对知识 的追求和欲望度。短暂的一个星期过去了，我完成了门己的通信网基础课程设计，虽然 在这过程中遇到了许多得困难，但成功还是给我带來了更人得喜悦。相信我得通信网学 习之路不会就此结