最短路徑貪心動態(tài)規(guī)劃

最短途徑-貪心+動態(tài)規(guī)劃packagebbb;importjava.util.*;importjava.io.*;publicclassShortestPath{/******************************************************************************************最短途徑算法(貪心+動態(tài)規(guī)劃)*****************************************************************************************/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("請輸入圖中節(jié)點個數(shù):");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("動態(tài)規(guī)劃求解");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;i<num;i++){System.out.println("輸入第"+(i+1)+"個都市名稱可達都市及距離");BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));Strings=br.readLine();s=s.trim();String[]kkk=s.split("");/*for(intj=0;j<kkk.length;j++){System.out.println(kkk[j]);}*/Stringname=kkk[0];Nodenode=newNode(name);for(intj=1;j<kkk.length;j=j+2){node.addElement(kkk[j],kkk[j+1]);}al.add(node);}}publicArrayListgetNodes(){//獲得所有節(jié)點集returnthis.al;}}/*****************************************************************節(jié)點數(shù)據(jù)類*****************************************************************/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){=name;}publicvoidaddElement(StringnodeName,Stringdistance){hm.put(nodeName,distance);}publicStringgetName(){;}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("");}}/*****************************************************************途徑類，用于寄存起點抵達個節(jié)點旳距離，途徑*****************************************************************/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){=name;}publicStringgetName(){;}publicLinkedListgetPh(){returnph;}publicvoidsetPh(LinkedListph){this.ph=ph;}publicvoidprint(){System.out.println("抵達節(jié)點"+name+"旳距離是"+distance);System.out.print("途徑為:");for(inti=0;i<ph.size();i++){System.out.print(((Node)ph.get(i)).getName()+"");}System.out.println();}}/***算法類，Dijkstra算法和動態(tài)規(guī)劃旳多段圖最短途徑算法**/classAlgorithm{/*****************************************************************Dijkstra算法(貪心算法)*****************************************************************/publicstaticvoidDijkstra(ArrayListnodes){//貪心算法//LinkedListselectedSet=newLinkedList();Path[]path=newPath[nodes.size()];//初始化目旳節(jié)點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;i<nodes.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[i].setNode((Node)nodes.get(i));}//計算途徑for(inti=1;i<nodes.size();i++){inttemp=i;doubles=path[i].getDistance();for(intj=i+1;j<nodes.size();j++){//找到被選集中距離近來旳節(jié)點if(path[j].getDistance()<s){temp=j;s=path[j].getDistance();}}Noden=path[temp].getNode();path[temp].addElement(n);for(intj=i+1;j<nodes.size();j++){//調(diào)整距離doubled=n.getDistance(path[j].getNode());if(path[j].getDistance()>path[i].getDistance()+d){//調(diào)整途徑//通過新節(jié)點使得抵達該節(jié)點距離變短，途徑應(yīng)當沿抵達新節(jié)點途徑抵達該節(jié)點//有問題待調(diào)整LinkedListph=path[i].getPh();for(intk=1;k<ph.size();k++){path[j].addElement(((Node)ph.get(k)));}path[j].setDistance(path[i].getDistance()+d);}}swap(path,temp,i);}for(inti=0;i<nodes.size();i++){//輸出path[i].print();}}publicstaticvoidswap(Path[]p,inttemp,intj){//互換名字Stringn=p[temp].getName();p[temp].setName(p[j].getName());p[j].setName(n);//換距離doubled=p[temp].getDistance();p[temp].setDistance(p[j].getDistance());p[j].setDistance(d);//換節(jié)點Nodenode=p[temp].getNode();p[temp].setNode(p[j].getNode());p[j].setNode(node);//換途徑LinkedListph=p[temp].getPh();p[temp].setPh(p[j].getPh());p[j].setPh(ph);}/*****************************************************************動態(tài)規(guī)劃旳多段圖最短途徑算法*****************************************************************/publicstaticvoidMultistageGraphShortestPath(ArrayListnodes){//Path2[]path=newPath2[nodes.size()];LinkedListal=newLinkedList();//初始化for(inti=0;i<nodes.size()-1;i++){Nodenode=(Node)nodes.get(i);node.setCost(Double.MAX_VALUE);node.setPath(null);}Nodenode=(Node)nodes.get(nodes.size()-1);node.setCost(0);node.setPath(null);node.setFlag(true);for(inti=0;i<nodes.size()-1;i++){Stringname=((Node)nodes.get(i)).canGet((Node)nodes.get(nodes.size()-1));if(!name.equals("")){al.add((Node)nodes.get(i));}}//計算for(inti=0;al.size()!=0;i++){booleanflag=true;Nodenext=null;Nodetemp=null;node=(Node)al.getFirst();al.removeFirst();String[]s=node.getNext().trim().split("");doublecost=node.getCost();for(intj=0;j<s.length;j=j+2){for(intk=0;k<nodes.size();k++){temp=(Node)nodes.get(k);if((temp.getName().equals(s[j]))){if(!temp.isFlag())flag=false;else{i