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

《最短路径-贪心+动态规划.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、packagebbb;importjava.util.*;importjava.io.*;publicclassShortestPath{/******************************************************************************************最短路径算法（贪心+动态规划）*****************************************************************************************/publicstaticvoidm

2、ain(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("请输入图中节点个数

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("动态规划求解");System.out.println("************************************************************");Algorithm.MultistageGraphShortestPath(node);}}/******************

5、***********************************************图管理类*****************************************************************/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");//北京到沈阳node2.addElement(node3.getName(),"5");//上海到沈阳node2.addElement(node4.getName(),"20");//上海到长春node3.addElement(node4.getName(),"5");//沈阳到长春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("输入各城市的名称可达城市及距离格式：城市名称可达城市1达城市1的距离可达城市2达城市2的距离。。。。。以空格分隔");System.out.println("例如：北京上海100南京50表示北京到达上海100公里到达南京50公里");for(inti=0;i

8、ntln("输入第"+(i+1)+"个城市名称可达城