最短路径算法记录多条路径
在使用Dijkstra算法计算最段路径的时候，如果只有多条最段路径默认只能输出一条，其实只要修改一下代码就可以得到多条最段路径。
?
?
public ArrayList<ArrayList<Node>> ?shortPathAstar(Node src,Node des){
open.clear();
closed.clear();
open.add(src);
while(open.size() > 0){
float lowest = Float.MAX_VALUE;
int c = -1;
//找到Open列表中当前路径最小值节点
for(int i = 0; i < open.size(); i++){
Node temp = (Node) open.get(i);
if(temp.getF() < lowest){
lowest = temp.getF();
c = i;
}
}
? ?
Node current = (Node) open.remove(c);
closed.add(current);
if(current.equals(des)){
break;
}
for(int i = 0; i < current.getLinks().size(); i++){
Connector a = (Connector) current.getLinks().get(i);
Node adjacent = a.getDes();
if(!arrayListContains(closed, adjacent)){
if(!arrayListContains(open, adjacent)){//不在open表中
open.add(adjacent);
adjacent.setParenet(current);
adjacent.setF(current.getF()+a.getDistance());
}else{//在open表中
if(adjacent.getF() > current.getF()+a.getDistance()){
adjacent.setParenet(current);
adjacent.setF(current.getF()+a.getDistance());
}else if(adjacent.getF() == current.getF()+a.getDistance()){
//如果相等于把其放入到open 表中，以便能搜索多条最短路径
?//主要的策略是复制一个节点，并把这个节点放入到候选的open表中作为
//又一个候选节点
Node dup = new Node(adjacent.getName());
dup.setParenet(current);
dup.setF(current.getF()+a.getDistance());
dup.setLinks(adjacent.getLinks());
open.add(dup);
}
}//end if
}//end if
}//end For
}//end while
ArrayList<ArrayList<Node>> path = new ArrayList<ArrayList<Node>>();
Node pathNode = des;
ArrayList<Node> result = new ArrayList<Node>();
while(pathNode != null){
result.add(pathNode);
pathNode = pathNode.getParenet();
}
Collections.reverse(result);
path.add(result);
//找到多条最短的路径
for(Node node:open){
ArrayList<Node> temp = new ArrayList<Node>();
if(node.equals(des)){
while(node != null){
temp.add(node);
node = node.getParenet();
}
Collections.reverse(temp);
path.add(temp);
}
}
return path;
}
?
?
