北交计算机网络13281069编程实现路由算法.docx

《北交计算机网络13281069编程实现路由算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编程实现路由算法一、实验目的运用各种编程语言实现基于Dijkstra算法的路由软件。二、实验意义通过本实验，使学生能够对路由原理和路由算法有进一步的理解和掌握。三、实验背景Dijkstra算法描述如下：设：c(i,j):结点i至结点j之间链路的代价，若i,j不直接相连，则为无穷大。D(v):当前从源结点至目的结点V之间路由的代价。p(v):从源结点至目的结点V之间路由中V之前的结点N:已经知道最优路径的结点集合1Initialization:2N={A}3forallnodesv4ifvadjacenttoA5thenD(v)=c(A,v)6elseD(v)=infty7Loop8f

2、indwnotinNsuchthatD(w)isaminimum9addwtoN10updateD(v)forallvadjacenttowandnotinN:11D(v)=min(D(v),D(w)+c(w,v))12/*newcosttoviseitheroldcosttovorknown13shortestpathcosttowpluscostfromwtov*/14untilallnodesinN四、实验步骤1.选择合适的编程语言编程实现基于Dijkstra算法的路由软件。2.输入不同的网络拓扑和链路代价测试和验证自己的路由软件。一、设计方法Dijkstra(迪杰斯特拉)算法

3、是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。本实验使用OPEN,CLOSE表方式来实现Dijkstra算法，其采用的是贪心法的算法策略，过程如下：1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点2.初始阶段，从键盘输入节点、边、权值、初始节点等信息，使用MapBuilder类初始化数据源，用Node对象封装节点信息，包括名字和子节点，将初始节点放入close，其他所有节点放入open，并返回图的起始节点。3.从open中选出"距离最短的顶点k"，并将顶

4、点k加入到close中；同时，从open中移除顶点k。4.更新open中各个顶点到起点的距离。之所以更新open中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离。5.重复步骤(3)和(4)，直至close包含所有子节点。六、类概览与描述（1）Node类：用于封装节点信息，包括节点名name和子节点child两个属性。child表示和此结点相邻的结点以及两个结点之间的代价，主要功能函数为对两各私有属性的set和get函数。（2）MapBuilder类：用于初始化数据源，返回图的起始节点。主要功能函数为：publicNodebuild(Set<

5、Node>open,Setclose,Mapnodes)用于接收从键盘输入的节点个数，节点名称，边的条数，边的信息，起始点等信息，并将节点名，节点与其子节点之间的代价存入Node对象之中，将起始点存储到close变量中，其它节点存储到open变量中。（3）Dijkstra类：实现核心功能，open属性用来存储尚未加入最短路径的节点，close属性存储已加入最短路径的节点，path属性用来封装各节点到起始节点的路径距离，pathInfo属性用来保存路径信息（起始点到各目标节点的最短路径上的路由器名称）。该类用于计算起始节点到所有其他节点的最短路径。

6、主要功能函数有：A.publicvoidinit()：初始化路径，调用MapBuilder类中的build函数，将初始节点放入close,其他节点放入open中，并且对于open中的每一个节点，将其到起始点的路径距离存入path变量中（若与起始点不相邻，则距离设置Integer.MAX_VALUE），路径信息存入pathInfo变量中。B.publicvoidcomputePath()：计算起始节点到所有其他节点的最短路径和路径信息。首先调用getShortestPath函数，获取到距离最近的子节点，存入close变量之中，然后更新open中各个顶点到起点的距离，递归调用comput

7、ePath函数向外一层层递归,直至所有顶点被遍历。C.privateNodegetShortestPath()：获得与当前结点最近的子结点,并返回该节点。D.publicvoidprintPathInfo()：输出起始点到其他结点的最短路径。七、实验测试结果与分析测试所用图的结构如下：程序运行之后通过调用Dijkstra类中的publicvoidinit()函数初始化，输入节点个数、节点名称、边的条数、边的权值信息以及起点，将节点的信息、与其相邻的节点以及