编程实现路由算法

《编程实现路由算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、importjava.util.ArrayList;importjava.util.LinkedHashMap;publicclassshutPath{staticint[][]cost;staticArrayListvisited=newArrayList();staticArrayListunVisited=newArrayList();staticArrayListvertexs=newArrayList

2、g>();staticLinkedHashMapshortPath=newLinkedHashMap();staticArrayListarcs=newArrayList();staticLinkedHashMapshortPathWay=newLinkedHashMap();publicstaticvoidmain(String[]args){//TODOA

3、uto-generatedmethodstub//initthevergessetarcs.add(newarc("A","B",2));arcs.add(newarc("A","C",4));arcs.add(newarc("A","D",15));arcs.add(newarc("B","D",5));arcs.add(newarc("B","C",1));arcs.add(newarc("C","D",7));arcs.add(newarc("D","E",4));//initthenodess

4、etvertexs.add("A");vertexs.add("B");vertexs.add("C");vertexs.add("D");vertexs.add("E");//initthenovisitedsetvisited.add("A");//initthevisitedsetunVisited.add("B");unVisited.add("C");unVisited.add("D");unVisited.add("E");//inittheshortPathmapfor(Stringun

5、visitNode:unVisited){booleanaccess=false;for(arca:arcs){if(a.startNode.equals("A")&&a.endNode.equals(unvisitNode)){shortPath.put(unvisitNode,a.weight);access=true;break;}}if(access==false){shortPath.put(unvisitNode,-1);}}//把第一个临近节点的前驱找到initFirstShortPat

6、hWay();while(unVisited.size()>0){StringlastVisitedNode=getLastVisitedNode();for(StringunvisitNode:unVisited){//获得最后一访问节点到未访问节点到距离intnewPath=getWeight(lastVisitedNode,unvisitNode);if(newPath>0){//获得源点到未访问节点的距离intoldPath=getOldPath(unvisitNode);//如果二者都存在话

7、，改变shortPath的相应值为最小值if(oldPath>0){if(oldPath>getOldPath(lastVisitedNode)+newPath){resetShortPath(unvisitNode,getOldPath(lastVisitedNode)+newPath);shortPathWay.put(unvisitNode,lastVisitedNode);//后继——前驱}}//如果原来不可达的话，但是通过中间节点可以到达，那么同样要改变shortPathelse{reset

8、ShortPath(unvisitNode,getOldPath(lastVisitedNode)+newPath);shortPathWay.put(unvisitNode,lastVisitedNode);}}}StringminNode=getTheMinPathNode();removeNode(minNode,unVisited);addNode(minNode,visited);}//输出最终结果printResult();}//初始化第一个