java快速易懂寻路算法

import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; /** * * @author 孤云挂月 * 寻路算法很多，没有什么高深的技术，仅仅是提供一个能用的自编算法 * 可以用来查找相关连的所有路径及最短路径的，可以正查也可以逆查 * 耗时相对也比较短 * * */ public class ShowMeTheWay { /** * @param args */ private List<Line> link=new ArrayList<Line>(); private Line target=null; private String result=null; public boolean addLine(Line line){ //应添加节点连接是否已添加过 link.add(line); //System.out.println("line:" + line.getPoint_1() + line.getPoint_2()); System.out.println("line:" + line.toString()); return true; } public void setTarget(Line line){ System.out.println("target:" + line.toString()); target=line; } public void display(){ System.out.println("最短路径:" + result); } public void calculation(){ System.out.println("calculation start:" + System.currentTimeMillis()); Map<String,LineSet> map=new HashMap<String,LineSet>(); for(int i=0;i<link.size();i++){ Line tmp=link.get(i); //端点1 增加映射 LineSet ls_1 =map.get(tmp.getPoint_1()); if(ls_1==null){ LineSet ls=new LineSet(); ls.setVertex(tmp.getPoint_1()); ls.addLine(tmp.getPoint_2()); map.put(tmp.getPoint_1(), ls); }else{ //if(ls_1.checkLine(tmp.getPoint_2())==false){ ls_1.addLine(tmp.getPoint_2()); //} } //端点2 增加映射 LineSet ls_2 =map.get(tmp.getPoint_2()); if(ls_2==null){ LineSet ls=new LineSet(); ls.setVertex(tmp.getPoint_2()); ls.addLine(tmp.getPoint_1()); map.put(tmp.getPoint_2(), ls); }else{ //if(ls_2.checkLine(tmp.getPoint_1())==false){ ls_2.addLine(tmp.getPoint_1()); //} } } List<LineSet> rList=new ArrayList<LineSet>(); boolean flag=false; LinkedList<LineSet> ll=new LinkedList<LineSet>(); LineSet ls=map.get(target.getPoint_1()); if(ls==null){ System.out.println("无此端点"); return ; } for(int o=0;o<ls.getList().size();o++){ if(ls.getList().toArray()[o].equals(target.getPoint_2())){ result=target.getPoint_1() + "->" +target.getPoint_2(); flag=true; break; }else{ LineSet tls=new LineSet(); tls.setVertex((String) ls.getList().toArray()[o]); tls.makeResult(target.getPoint_1()); tls.addLine(target.getPoint_1()); //tls.addLine((String) ls.getList().toArray()[o]); ll.add(tls); } } while(flag==false){ LinkedList<LineSet> tll=new LinkedList<LineSet>(); while(ll.size()!=0){ LineSet vv=ll.pop(); LineSet _tls =map.get(vv.getVertex()); for(int m=0;m<_tls.getList().size();m++){ LineSet v=new LineSet(); v.setVertex(vv.getVertex()); v.setLines(vv.getLines()); v.setResult(vv.getResult()); if(v.checkLine((String)_tls.getList().toArray()[m])){ v.addLine(v.getVertex()); v.makeResult(v.getVertex()); //v.makeResult((String)_tls.getList().toArray()[m]); v.setVertex((String)_tls.getList().toArray()[m]); tll.add(v); if(((String)_tls.getList().toArray()[m]).equals(target.getPoint_2())){ v.makeResult((String)_tls.getList().toArray()[m]); rList.add(v); //System.out.println(v.getResult()); //System.out.println(v.getResult()); //System.out.println("==================================="); }//else{ //System.out.println(v.getResult()); //} //System.out.println(v.getResult()); } } } //System.out.println("1"); if(tll.size()==0){ flag=true; break; }else{ ll=tll; } } System.out.println("结果个数:"+rList.size()); int sResult=-1; for(int n=0;n<rList.size();n++){ if(sResult==-1){ sResult=0; result=rList.get(0).getResult(); }else{ if(rList.get(n).getResult().length()<result.length()){ sResult=n; result=rList.get(0).getResult(); } } System.out.println("第"+(n+1)+"种路径:"+rList.get(n).getResult()); } //if(sResult!=-1){ // System.out.println("最短路径:"+result); //} System.out.println("calculation finish:" + System.currentTimeMillis()); } public static void main(String[] args) { ShowMeTheWay smt=new ShowMeTheWay(); /* smt.addLine(new Line("1","2")); smt.addLine(new Line("1","3")); smt.addLine(new Line("2","3")); smt.addLine(new Line("3","4")); smt.addLine(new Line("5","4")); smt.setTarget(new Line("3","5")); */ //只需要输入所有点之间的链接(无顺序要求,不限于数字输入) smt.addLine(new Line("0", "1")); smt.addLine(new Line("0", "2")); smt.addLine(new Line("1", "3")); smt.addLine(new Line("1", "4")); smt.addLine(new Line("1", "9")); smt.addLine(new Line("3", "4")); smt.addLine(new Line("3", "5")); smt.addLine(new Line("2", "5")); smt.addLine(new Line("5", "6")); smt.addLine(new Line("6", "7")); smt.addLine(new Line("7", "8")); smt.addLine(new Line("4", "9")); //输入起始点 smt.setTarget(new Line("2","9")); smt.calculation(); //显示结果 smt.display(); } }