文档介绍：课程设计说明书
最短路径 Dijkstra算法
为了巩固“数据通信与通信网技术”课程学到的相关知识,通过对本课程所学知识的综合运用,使学生融会贯通课程中所学的理论知识,初步掌握通信网络的体系结构和扩频通信系统等相关知识;加深对通信网络的基本理论、基本知识和常用技术的理解;提高学生分析问题的能力和实践能力,培养科学研究的独立工作能力。
本次课程设计,我采用了eclipse--Java软件,利用迪杰斯特(Dijkstra)算法,来解决最短路径问题。迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。
Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。幸运的是,Eclipse 附带了一个标准的插件集,包括 Java 开发工具(Java Development Tools,JDT)。Java是由Sun Microsystems公司于1995年5月推出的Java程序设计语言(以下简称Java语言)和Java平台的总称。用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中任意顶点的最短路径长度。
Dijkstra算法原理
,引入一个辅助向量D,它的每个分量 D[i]表示当前所找到的从起始点V(即源点 V )到其它每个顶点Vi 的长度。
例如,D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。
D的初始状态为:若从 V到Vi有弧(即从V到Vi 存在连接边),则D [i]为弧上的权值(即为从V 到Vi 的边的权值);否则置D [i]为∞。显然,长度为D [j] = Min{ D |Vi ∈V } 的路径就是从V出发到顶点 Vj 的长度最短的一条路径,此路径为( V,V[j])。
,下一条长度次短的是哪一条呢?也就是找到从源点V到下一个顶点的最短路径长度所对应的顶点,且这条最短路径长度仅次于从源点 V到顶点Vj 的最短路径长度。假设该次短路径的终点是 Vk ,则可想而知,这条路径要么是( V,Vk ),或者是(V,Vj,Vk )。它的长度或者是从V到Vk的弧上的权值,或者是D[j] 加上从 Vj 到 Vk 的弧上的权值。
,假设S为已求得的从源点V 出发的最短路径长度的顶点的集合,则可证明:下一条次最短路径(设其终点为X )要么是弧(V,X ),或者是从源点V 出发的中间只经过S中的顶点而最后到达顶点X的路径。因此,下一条长度次短的的最。
沈阳大学
课程设计说明书
短路径长度必是D[j] = Min{ D[i] | Vi ∈V-S },其中D[i]要么是弧( V, Vi  )上的权值,或者是D[k] ( Vk  ∈S)和弧( Vk , Vi  )上的权值之和
算法描述如下:
1)令arcs表示弧上的权值。若弧不存在,则置arcs为∞(在本程序中为MAXCOST)。S为已找到的从V 出发的的终点的集合,初始状态为空集。那么,从V 出发到图上其余各顶点 Vi可能达到的长度的初值为D=arcs[Locat