文档介绍：课程设计说明书最短路径 Dijkstra 算法 1. 课程设计的目的为了巩固“数据通信与通信网技术”课程学到的相关知识,通过对本课程所学知识的综合运用,使学生融会贯通课程中所学的理论知识,初步掌握通信网络的体系结构和扩频通信系统等相关知识;加深对通信网络的基本理论、基本知识和常用技术的理解; 提高学生分析问题的能力和实践能力,培养科学研究的独立工作能力。 2. 设计方案论证本次课程设计,我采用了 eclipse--Java 软件,利用迪杰斯特( Dijkstra )算法,来解决最短路径问题。迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于 1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。幸运的是,Eclipse 附带了一个标准的插件集,包括 Java 开发工具(Java Development Tools ,JDT) 。Java 是由 Sun Microsystem s公司于199 5年5月推出的Jav a 程序设计语言(以下简称Jav a语言)和Jav a 平台的总称。用 Java 实现的 HotJava 浏览器( 支持 Java applet) 显示了 Java 的魅力: 跨平台、动态的 Web 、计算。从此,Java 被广泛接受并推动了 Web 的迅速发展, 常用的浏览器现在均支持 Java applet 。另一方面, Java 技术也不断更新,面向对象的可视化集成编程系统。它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点,而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2 ,WinSock 网络等。迪杰斯特拉算法介绍: 迪杰斯特拉算法是典型最短路径算法,用于计算图或网中某个特定顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外,层层扩展,直到扩展覆盖所有顶点。设G=(V,E) 为一个带全有向图,把图中顶点集合 V分成两组。第一组为已求出最短路径沈阳大学课程设计说明书 NO2 的顶点集合。用S表示,初始时 S中只有一个源点,以后每求得一条最短路径,就将所到达最短路径的顶点加入到集合 S 中,直到全部顶点都加入到 S 中。第二组为其余未确定最短路径的顶点集合。用U 表示, U=V-S ,U 中的顶点不断的加入到 S 中,直到U为空,S=V 。在U加入 S的过程中,始终保持源点到 S中各顶点的最短路径长度小于或等于源点到 U中任意顶点的最短路径长度。 3. 设计的过程与分析 Dijkstra 算法原理 ,引入一个辅助向量 D,它的每个分量 D[i] 表示当前所找到的从起始点 V (即源点 V)到其它每个顶点 V i的长度。例如, D[3] =2表示从起始点到顶点 3的路径相对最小长度为 2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。 :若从 V到V i有弧(即从 V到V i存在连接边),则 D[i] 为弧上的权值(即为从 V到V i的边的权值);否则置 D[i] 为∞。显然,长度为 D[j] =Min{ D|V i∈V}的路径就是从 V出发到顶点 V j的长度最短的一条路径,此路径为(V,V [j])。 ,下一条长度次短的是哪一条呢?也就是找到从源点 V到下一个顶点的最短路径长度所对应的顶点,且这条最短路径长度仅次于从源点 V到顶点 V j的最短路径长度。假设该次短路径的终点是 V k,则可想而知,这条路径要么是(V ,V k), 或者是(V,V j,V k)。它的长度或者是从 V到V k的弧上的权值,或者是 D [j]加上从V j到V k的弧上的权值。 ,假设 S为已求得的从源点 V出发的最短路径长度的顶点的集合,则可证明:下一条次最短路径(设其终点为 X )要么是弧(V,X ) ,或者是从源点 V出发的中间只经过 S中的顶点而最后到达顶点 X的路径。因此,下一条长度次短的的最。沈阳大学课程设计说明书短路径长度必是 D [j]=Min{ D [i]|V i∈V-S },其中 D [i]要么是弧(V,V i)上的权值,或者是 D [k](V k∈S)和弧(V k,V i)上的权值之和算法描述如下: 1)令arcs 表示弧上的权值。若弧不存在,则置 arcs 为∞(在本程序中为 MAXCOST )。 S为已找到的从 V出发的的终点的集合,初始状态为空集。那么,