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();
}
}
