资源描述：
《通信网基础及应用课程设计模板1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、课程设计说明书NO,1基于Vc++最短路径Dijkstra算法的实现1•课程设计的目的为了巩固“通信网基础及应用”课程学到的相关知识，通过对本课程所学知识的综合运用，使学牛融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和扩频通信系统等相关知识；加深对通信网络的基本理论、基本知识和常用技术的理解；提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力。2.设计方案论证2.1问题描述给定一个带权无向图G=(V,E),其屮每条边的权是一个非负实数。另外，还给定V中的一个项点，称为源。现在我们耍计算从源到所有其他各项点的最短路径长度。这里的长度是指路上各边权之和。这
2、个问题通常称为单源最短路径问题。2.2算法介纟召Dijkstra算法是由荷兰计算机科学家艾兹格•迪科斯彻发现的。算法解决的是有向图中最短路径问题。例如，如果图中的顶点表示城市，而边上的权重表示著城市间开车路经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w:E[0,定义。因此w(u,v)就是从顶点u到顶点v的非负花费值
3、(cost)o边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t,Dijkstra算法可以找到s至ijt的最低花费路径(i.e.最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。2.3算法描述这个算法是通过为每个顶点V保留目前为止所找到的从S到V的最短路径来工作的。初始时，源点S的路径长度值被赋为0(d[s]二0),同吋把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径(对于V屮所有顶点v除s外d[v]=-)o当算法结束时，d[v]中储存的便是从s到v的最短
4、路径，或者如果路径不存在的话是无穷大。Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边,那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)o如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]屮的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。算法维护两个顶点集S和Qo集合S保留了我们己知的所有d[v]的值己经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状
5、态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q屮拥有最小的d[u]值的顶点。当一个顶点U从Q中转移到了S中，算法对每条外接边(u,V)进行拓展。2.4Dijkstra算法计算过程Dijkstra算法是一种最短路径算法，用于计算一个节点到其它所有节点的最短路。算法本身并不是按照我们的正常思维习惯，我们一般会，从原点遍历所有与之相连的节点，找到最短路径，再从最短路径上的那个点遍历与之相连的所有其它点(原点除外)，然后依次类推。这样做虽然可以算出一个树形，但是在大多数情况下，这种算法会产生很多次优路径，也就是说非最短路径。Dijkstra算法的大概过程：假设两个
6、表，表A和表B表A表示牛成路径，表B表示最后确定的路径1.从原点出发，遍历检查所有与之相连的节点，将原点和这些节点存放到表A中，并记录下两节点Z间的代价。2•将代价最小的代价值和这两节点移动到表B中(其中一个是原点)。3.把这个节点所连接的子节点找出，放入到表A中，算出子节点到原点的代价4.重复第二步和第三步直到表A为空。然后根据表B中的数据算出最优树。Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径长度d[u]+讥u,v)。如果这个值比目前已知的d[v]的值要小,我们
7、可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次.Dijkstra算法是解单源最短路径问题的一个算法。2.5相关问题和算法在Dijkstra算法的基础上作一些改动，可以扩展其功能。OSPF(openshortestpathfirst,开放最短路径优先)算法是Dijkstra算法在网络路由中的一个具体实现。与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，
