编程实现路由算法

importjava.util.ArrayList;importjava.util.LinkedHashMap;publicclassshutPath{staticint[][]cost;staticArrayListStringvisited=newArrayListString();staticArrayListStringunVisited=newArrayListString();staticArrayListStringvertexs=newArrayListString();staticLinkedHashMapString,IntegershortPath=newLinkedHashMapString,Integer();staticArrayListarcarcs=newArrayListarc();staticLinkedHashMapString,StringshortPathWay=newLinkedHashMapString,String();publicstaticvoidmain(String[]args){//TODOAuto-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));//initthenodessetvertexs.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(StringunvisitNode: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);}}//把第一个临近节点的前驱找到initFirstShortPathWay();while(unVisited.size()0){StringlastVisitedNode=getLastVisitedNode();for(StringunvisitNode:unVisited){//获得最后一访问节点到未访问节点到距离intnewPath=getWeight(lastVisitedNode,unvisitNode);if(newPath0){//获得源点到未访问节点的距离intoldPath=getOldPath(unvisitNode);//如果二者都存在话，改变shortPath的相应值为最小值if(oldPath0){if(oldPathgetOldPath(lastVisitedNode)+newPath){resetShortPath(unvisitNode,getOldPath(lastVisitedNode)+newPath);shortPathWay.put(unvisitNode,lastVisitedNode);//后继——前驱}}//如果原来不可达的话，但是通过中间节点可以到达，那么同样要改变shortPathelse{resetShortPath(unvisitNode,getOldPath(lastVisitedNode)+newPath);shortPathWay.put(unvisitNode,lastVisitedNode);}}}StringminNode=getTheMinPathNode();removeNode(minNode,unVisited);addNode(minNode,visited);}//输出最终结果printResult();}//初始化第一个路径的前驱publicstaticvoidinitFirstShortPathWay(){intmin=500;StringfirstNode=;for(Stringvertex:shortPath.keySet()){inttem=shortPath.get(vertex);if(tem0){min=mintem?tem:min;}}for(Stringvertex:shortPath.keySet()){if(min==shortPath.get(vertex))firstNode=vertex;}shortPathWay.put(firstNode,A);}//addanodetothesetpublicstaticvoidaddNode(Stringnode,ArrayListStringset){set.add(node);}//removeanodeofthesetpublicstaticvoidremoveNode(StringdelNode,ArrayListStringset){intindex=0;for(inti=0;iset.size();i++){if(delNode.equals(set.get(i))){index=i;}}set.remove(index);}//得到未访问结点中shutPath的最小值的点publicstaticStringgetTheMinPathNode(){intmin=500;//距离超过500为不可达Stringnode=;for(Stringunode:unVisited){inttem=shortPath.get(unode);if(tem0){min=mintem?tem:min;}}for(Stringunode:unVisited){if(min==shortPath.get(unode))node=unode;}returnnode;}//得到源点到未访问结点的最短距离publicstaticintgetOldPath(Stringnode){if(node.equals(A))return0;returnshortPath.get(node);}//重新设定shortPathpublicstaticvoidresetShortPath(Stringnode,intpath){for(Stringsnode:shortPath.keySet()){if(snode.equals(node))shortPath.put(snode,path);}}//getthelastnodeofthevisitedsetpublicstaticStringgetLastVisitedNode(){returnvisited.get(visited.size()-1);}//gettheweightpublicstaticintgetWeight(StringstartNode,StringendNode){intweight=-1;for(arca:arcs){if(a.startNode.equals(startNode)&&a.endNode.equals(endNode)){weight=a.weight;System.out.println(a.startNode+--+a.endNode+=+weight);}}returnweight;}//gettheminnumpublicstaticvoidprintResult(){for(Stringvertex:shortPath.keySet()){System.out.print(从源点A到+vertex+的最短路径为);printPath(vertex);System.out.print(vertex);System.out.print(长度为：+shortPath.get(vertex));System.out.println();}}publicstaticvoidprintPath(Stringvertex){Stringnode=shortPathWay.get(vertex);if(!node.equals(A))printPath(node);System.out.print(node+);}}classarc{StringstartNode=;StringendNode=;intweight=0;publicarc(StringstartNode,StringendNode,intweight){this.startNode=startNode;this.endNode=endNode;this.weight=weight;}}实验结果（截图）：实验感想：Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等，我主要是通过数据结构和离散数学的图论得到的结果。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。