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

编程实现路由算法一、实验目的运用各种编程语言实现基于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)=infty7Loop8findwnotinNsuchthatD(w)isaminimum9addwtoN10updateD(v)forallvadjacenttowandnotinN:11D(v)=min(D(v),D(w)+c(w,v))12/*newcosttoviseitheroldcosttovorknown13shortestpathcosttowpluscostfromwtov*/14untilallnodesinN四、实验步骤1.选择合适的编程语言编程实现基于Dijkstra算法的路由软件。2.输入不同的网络拓扑和链路代价测试和验证自己的路由软件。五、设计方法Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。本实验使用OPEN,CLOSE表方式来实现Dijkstra算法，其采用的是贪心法的算法策略，过程如下：1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点2.初始阶段，从键盘输入节点、边、权值、初始节点等信息，使用MapBuilder类初始化数据源，用Node对象封装节点信息，包括名字和子节点，将初始节点放入close，其他所有节点放入open，并返回图的起始节点。3.从open中选出距离最短的顶点k，并将顶点k加入到close中；同时，从open中移除顶点k。4.更新open中各个顶点到起点的距离。之所以更新open中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离。5.重复步骤(3)和(4)，直至close包含所有子节点。六、类概览与描述（1）Node类：用于封装节点信息，包括节点名name和子节点child两个属性。child表示和此结点相邻的结点以及两个结点之间的代价，主要功能函数为对两各私有属性的set和get函数。（2）MapBuilder类：用于初始化数据源，返回图的起始节点。主要功能函数为：publicNodebuild(SetNodeopen,SetNodeclose,MapString,Nodenodes)用于接收从键盘输入的节点个数，节点名称，边的条数，边的信息，起始点等信息，并将节点名，节点与其子节点之间的代价存入Node对象之中，将起始点存储到close变量中，其它节点存储到open变量中。（3）Dijkstra类：实现核心功能，open属性用来存储尚未加入最短路径的节点，close属性存储已加入最短路径的节点，path属性用来封装各节点到起始节点的路径距离，pathInfo属性用来保存路径信息（起始点到各目标节点的最短路径上的路由器名称）。该类用于计算起始节点到所有其他节点的最短路径。主要功能函数有：A.publicvoidinit()：初始化路径，调用MapBuilder类中的build函数，将初始节点放入close,其他节点放入open中，并且对于open中的每一个节点，将其到起始点的路径距离存入path变量中（若与起始点不相邻，则距离设置Integer.MAX_VALUE），路径信息存入pathInfo变量中。B.publicvoidcomputePath()：计算起始节点到所有其他节点的最短路径和路径信息。首先调用getShortestPath函数，获取到距离最近的子节点，存入close变量之中，然后更新open中各个顶点到起点的距离，递归调用computePath函数向外一层层递归,直至所有顶点被遍历。C.privateNodegetShortestPath()：获得与当前结点最近的子结点,并返回该节点。D.publicvoidprintPathInfo()：输出起始点到其他结点的最短路径。七、实验测试结果与分析测试所用图的结构如下：程序运行之后通过调用Dijkstra类中的publicvoidinit()函数初始化，输入节点个数、节点名称、边的条数、边的权值信息以及起点，将节点的信息、与其相邻的节点以及两个节点之间的代价存到Node对象之中。然后使用publicvoidcomputePath()函数计算起始节点到所有其他节点的最短路径，最后输出最短路径信息。从输出结果中可以得出A到各个节点的最短路径，经检验结果正确。八、实验总结通过本次实验，我对Dijkstra算法有了更深的理解，Dijkstra算法是迭代算法，通过设定两个集合open和close用来存储尚未加入最短路径的节点和已加入最短路径的节点，通过一次次迭代找到距离最近的子结点，加入到close中，并更新open中节点到起始点的距离，直至所有节点都被加入到close中，得到起始点到所有其它节点的最短路径。九、实验代码Node类用于封装节点信息，包括节点名和子节点：importjava.util.HashMap;importjava.util.Map;publicclassNode{privateStringname;//结点的名称privateMapNode,Integerchild=newHashMapNode,Integer();//child表示和此结点相邻的结点以及两个结点之间的代价publicNode(Stringname){this.name=name;}publicStringgetName(){returnname;}publicvoidsetName(Stringname){this.name=name;}publicMapNode,IntegergetChild(){returnchild;}publicvoidsetChild(MapNode,Integerchild){this.child=child;}}MapBuilder用于初始化数据源，返回图的起始节点：importjava.util.*;publicclassMapBuilder{publicNodebuild(SetNodeopen,SetNodeclose,MapString,Nodenodes){//通过外接输入整个图的信息Scannerscanner=newScanner(System.in);System.out.print(请输入节点个数：);intnum1=scanner.nextInt();//num1存节点个数scanner.nextLine();System.out.println(请输入节点名称：);Stringname=null;for(inti=0;inum1;i++){//输入节点名称name=scanner.nextLine();Nodenode=newNode(name);nodes.put(name,node);}System.out.print(请输入边的条数：);intnum2=scanner.nextInt();//num2存边的条数scanner.nextLine();System.out.println(请输入边的信息：);Stringline=null;for(inti=0;inum2;i++){line=scanner.nextLine();String[]xin=line.split();nodes.get(xin[0]).getChild().put(nodes.get(xin[1]),Integer.parseInt(xin[2]));nodes.get(xin[1]).getChild().put(nodes.get(xin[0]),Integer.parseInt(xin[2]));}System.out.println(设置起始点为：);name=scanner.nextLine();close.add(nodes.get(name));SetMap.EntryString,Nodesets=nodes.entrySet();for(Map.EntryString,Nodeentry:sets){Stringkey=(String)entry.getKey();Nodeval=(Node)entry.getValue();if(key.equals(name)){}else{open.add(val);//open变量存储尚未加入最短路径的结点}}returnnodes.get(name);//close变量存储的是已加入最短路径的结点}}Dijkstra对象用于计算起始节点到所有其他节点的最短路径importjava.util.*;publicclassDijkstra{SetNodeopen=newHashSetNode();SetNodeclose=newHashSetNode();MapString,Nodenodes=newHashMapString,Node();MapString,Integerpath=newHashMapString,Integer();//封装路径距离MapString,StringpathInfo=newHashMapString,String();//封装路径信息publicvoidinit(){//初始路径,因没有A-E这条路径,所以path(E)设置为Integer.MAX_VALUE//将初始节点放入close,其他节点放入openNodestart=newMapBuilder().build(open,close,nodes);MapNode,Integerstartmap=start.getChild();for(Nodenode:open){if(startmap.containsKey(node)){path.put(node.getName(),startmap.get(node));pathInfo.put(node.getName(),start.getName()+-+node.getName());}else{path.put(node.getName(),Integer.MAX_VALUE);pathInfo.put(node.getName(),start.getName());}}}publicvoidcomputePath(){Nodenearest=getShortestPath();//取距离start节点最近的子节点,放入closeclose.add(nearest);open.remove(nearest);if(nearest==null){return;}MapNode,Integerchilds=nearest.getChild();for(Nodechild:childs.keySet()){if(open.contains(child)){//如果子节点在open中IntegernewCompute=path.get(nearest.getName())+childs.get(child);if(path.get(child.getName())newCompute){//之前设置的距离大于新计算出来的距离path.put(child.getName(),newCompute);pathInfo.put(c