最短路徑-貪心+動(dòng)態(tài)規(guī)劃.doc

《最短路徑-貪心+動(dòng)態(tài)規(guī)劃.doc》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、packagebbb;importjava.util.*;importjava.io.*;publicclassShortestPath{/******************************************************************************************最短路徑算法（貪心+動(dòng)態(tài)規(guī)劃）*****************************************************************************************/publicstaticvoidm

2、ain(Stringargs[])throwsException{MyMapmm=newMyMap();System.out.println("1、使用默認(rèn)圖計(jì)算");System.out.println("2、鍵盤(pán)輸入一個(gè)圖計(jì)算");ArrayListnode=null;BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));if(br.readLine().equals("1")){mm.getGraph();}else{System.out.print("請(qǐng)輸入圖中節(jié)點(diǎn)個(gè)數(shù)

3、：");intnum=Integer.parseInt(br.readLine());mm.getGraph(num);}node=mm.getNodes();System.out.println("************************************************************");System.out.println("Dijkstra求解");System.out.println("************************************************************");Alg

4、orithm.Dijkstra(node);System.out.println("************************************************************");System.out.println("動(dòng)態(tài)規(guī)劃求解");System.out.println("************************************************************");Algorithm.MultistageGraphShortestPath(node);}}/******************

5、***********************************************圖管理類(lèi)*****************************************************************/classMyMap{ArrayListal=newArrayList();MyMap()throwsException{}publicvoidgetGraph(){Nodenode1=newNode("bj");Nodenode2=newNode("sh");Nodenode3=newNode("sy");Nodenode4=

6、newNode("cc");node1.addElement(node2.getName(),"10");//北京到上海node1.addElement(node3.getName(),"20");//北京到沈陽(yáng)node2.addElement(node3.getName(),"5");//上海到沈陽(yáng)node2.addElement(node4.getName(),"20");//上海到長(zhǎng)春node3.addElement(node4.getName(),"5");//沈陽(yáng)到長(zhǎng)春al.add(node1);al.add(node2);al.add(node3

7、);al.add(node4);//System.out.println(((Node)al.get(1)).getName());}publicvoidgetGraph(intnum)throwsException{System.out.println("輸入各城市的名稱(chēng)可達(dá)城市及距離格式：城市名稱(chēng)可達(dá)城市1達(dá)城市1的距離可達(dá)城市2達(dá)城市2的距離。。。。。以空格分隔");System.out.println("例如：北京上海100南京50表示北京到達(dá)上海100公里到達(dá)南京50公里");for(inti=0;i

8、ntln("輸入第"+(i+1)+"個(gè)城市名稱(chēng)可達(dá)城