最短路径算法记录多条路径

在使用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;

}