最短路径-贪心+动态规划

packagebbb;importjava.util.*;importjava.io.*;publicclassShortestPath{/******************************************************************************************最短路径算法（贪心+动态规划）*****************************************************************************************/publicstaticvoidmain(Stringargs[])throwsException{MyMapmm=newMyMap();System.out.println(1、使用默认图计算);System.out.println(2、键盘输入一个图计算);ArrayListnode=null;BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));if(br.readLine().equals(1)){mm.getGraph();}else{System.out.print(请输入图中节点个数：);intnum=Integer.parseInt(br.readLine());mm.getGraph(num);}node=mm.getNodes();System.out.println(************************************************************);System.out.println(Dijkstra求解);System.out.println(************************************************************);Algorithm.Dijkstra(node);System.out.println(************************************************************);System.out.println(动态规划求解);System.out.println(************************************************************);Algorithm.MultistageGraphShortestPath(node);}}/*****************************************************************图管理类*****************************************************************/classMyMap{ArrayListal=newArrayList();MyMap()throwsException{}publicvoidgetGraph(){Nodenode1=newNode(bj);Nodenode2=newNode(sh);Nodenode3=newNode(sy);Nodenode4=newNode(cc);node1.addElement(node2.getName(),10);//北京到上海node1.addElement(node3.getName(),20);//北京到沈阳node2.addElement(node3.getName(),5);//上海到沈阳node2.addElement(node4.getName(),20);//上海到长春node3.addElement(node4.getName(),5);//沈阳到长春al.add(node1);al.add(node2);al.add(node3);al.add(node4);//System.out.println(((Node)al.get(1)).getName());}publicvoidgetGraph(intnum)throwsException{System.out.println(输入各城市的名称可达城市及距离格式：城市名称可达城市1达城市1的距离可达城市2达城市2的距离。。。。。以空格分隔);System.out.println(例如：北京上海100南京50表示北京到达上海100公里到达南京50公里);for(inti=0;inum;i++){System.out.println(输入第+(i+1)+个城市名称可达城市及距离);BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));Strings=br.readLine();s=s.trim();String[]kkk=s.split();/*for(intj=0;jkkk.length;j++){System.out.println(kkk[j]);}*/Stringname=kkk[0];Nodenode=newNode(name);for(intj=1;jkkk.length;j=j+2){node.addElement(kkk[j],kkk[j+1]);}al.add(node);}}publicArrayListgetNodes(){//获得全部节点集returnthis.al;}}/*****************************************************************节点数据类*****************************************************************/classNode{Stringname;doublecost;Nodepath;booleanflag=false;publicdoublegetCost(){returncost;}publicvoidsetCost(doublecost){this.cost=cost;}publicNodegetPath(){returnpath;}publicvoidsetPath(Nodepath){this.path=path;}publicbooleanisFlag(){returnflag;}publicvoidsetFlag(booleanflag){this.flag=flag;}HashMaphm=newHashMap();publicNode(Stringname){this.name=name;}publicvoidaddElement(StringnodeName,Stringdistance){hm.put(nodeName,distance);}publicStringgetName(){returnthis.name;}publicdoublegetDistance(Noden){if(hm.get(((Node)n).getName().toString())!=null){returnDouble.parseDouble((hm.get(((Node)n).getName()).toString()));}elsereturnDouble.MAX_VALUE;}publicStringcanGet(Noden){if(hm.get(n.getName())!=null)returnthis.getName();returnnewString();}publicStringgetNext(){Strings=;Iteratoriter=hm.entrySet().iterator();if(iter.hasNext()){while(iter.hasNext()){Map.Entryelement=(Map.Entry)iter.next();ObjectstrKey=element.getKey();ObjectstrObj=element.getValue();s=s+strKey++strObj+;}returns;}returnnewString();}}/*****************************************************************路径类，用于存放起点到达个节点的距离，路径*****************************************************************/classPath{//用于计算Dijstra算法doubledistance;LinkedListph=newLinkedList();//booleanselect=false;Stringname;Nodenode=null;publicvoidaddElement(Noden){ph.add(n);}publicvoidsetDistance(doubled){distance=d;}publicdoublegetDistance(){returndistance;}publicvoidsetNode(Noden){node=n;}publicNodegetNode(){returnnode;}publicvoidsetName(Stringname){this.name=name;}publicStringgetName(){returnthis.name;}publicLinkedListgetPh(){returnph;}publicvoidsetPh(LinkedListph){this.ph=ph;}publicvoidprint(){System.out.println(到达节点+name+的距离是+distance);System.out.print(路径为：);for(inti=0;iph.size();i++){System.out.print(((Node)ph.get(i)).getName()+);}System.out.println();}}/***算法类，Dijkstra算法和动态规划的多段图最短路径算法**/classAlgorithm{/*****************************************************************Dijkstra算法(贪心算法)*****************************************************************/publicstaticvoidDijkstra(ArrayListnodes){//贪心算法//LinkedListselectedSet=newLinkedList();Path[]path=newPath[nodes.size()];//初始化目标节点path[0]=newPath();path[0].addElement((Node)nodes.get(0));path[0].setDistance(0);path[0].setName(((Node)nodes.get(0)).getName());path[0].setNode((Node)nodes.get(0));for(inti=1;inodes.size();i++){//初始化路径及距离path[i]=newPath();path[i].addElement((Node)nodes.get(0));Noden=(Node)nodes.get(i);doubled=((Node)nodes.get(0)).getDistance(n);path[i].setDistance(d);path[i].setName(((Node)nodes.get(i)).getName());path