在使用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;
}
分享到:
相关推荐
2.设置不同的地图,以及不同的初始状态和目标状态,记录A`算法的求解结果,包括最短路径、扩展节点数、生成节点数和算法运行时间。 3.对于相同的初始状态和目标状态,设计不同的启发式函数,比较不同启发式函数对迷宫寻路...
(6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method) (2)伙伴系统 (Buddy_system) (3)紧缩无用单元 (Storage_...
% 每⼀次迭代后的最短路径长度 L_best = inf.*ones(NC_max,1); % 每⼀次迭代后m只蚂蚁所得路径的平均值 L_ave = zeros(NC,1); while NC 将m只蚂蚁放到n个城市上 RandPosition = []; % ceil函数是向上取整,randperm...
例如,有些算法可以通过庞大的相连街道网络找到从起点到目的地的最短路径,或者有些搜索优化算法可以从数百万条记录中找到搜索结果。 数据结构是一种安排算法可以使用的数据的方式。 算法与数据结构紧密相关,因此...
"标节点的最短路径,但由 "标在前几条路径中那么该 "值找出代价最为小的一 " " "于盲目性大所以当搜索数 "搜索会较为快捷,在本搜 "条,所以很具优越性, " " "据比较多的时候该方法较 "索树中虽然比宽度优先少 ...
(6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method) (2)伙伴系统 (Buddy_system) (3)紧缩无用单元 (Storage_...
(6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method) (2)伙伴系统 (Buddy_system) (3)紧缩无用单元 (Storage_...
10.6 OSPF:开放最短路径优先 102 10.7 BGP:边界网关协议 103 10.8 CIDR:无类型域间选路 104 10.9 小结 105 第11章 UDP:用户数据报协议 107 11.1 引言 107 11.2 UDP首部 107 11.3 UDP检验和 108 11.3.1 tcpdump...
* 同一画布上的多条曲线。 * 转换工具(平移、旋转、缩放)。 * 精细的绘画能力。 还实现了其他有用的方法,例如 Lines、Circles 和 DataBalls,以及用于细分和通过数据球的最短/最平滑路径的工具。 现在,在 27 页...
10.6 OSPF:开放最短路径优先 10.7 BGP:边界网关协议 10.8 CIDR:无类型域间选路 10.9 小结 第11章 UDP:用户数据报协议 11.1 引言 11.2 UDP首部 11.3 UDP检验和 11.3.1 tcpdump输出 11.3.2 一些统计结果...
10.6 OSPF:开放最短路径优先 102 10.7 BGP:边界网关协议 103 10.8 CIDR:无类型域间选路 104 10.9 小结 105 第11章 UDP:用户数据报协议 107 11.1 引言 107 11.2 UDP首部 107 11.3 UDP检验和 108 11.3.1 tcpdump...
10.6 OSPF:开放最短路径优先 102 10.7 BGP:边界网关协议 103 10.8 CIDR:无类型域间选路 104 10.9 小结 105 第11章 UDP:用户数据报协议 107 11.1 引言 107 11.2 UDP首部 107 11.3 UDP检验和 108 11.3.1 tcpdump...
10.6 OSPF:开放最短路径优先 102 10.7 BGP:边界网关协议 103 10.8 CIDR:无类型域间选路 104 10.9 小结 105 第11章 UDP:用户数据报协议 107 11.1 引言 107 11.2 UDP首部 107 11.3 UDP检验和 108 11.3.1 tcpdump...
10.6 OSPF:开放最短路径优先 102 10.7 BGP:边界网关协议 103 10.8 CIDR:无类型域间选路 104 10.9 小结 105 第11章 UDP:用户数据报协议 107 11.1 引言 107 11.2 UDP首部 107 11.3 UDP检验和 108 11.3.1 tcpdump...
10.6 OSPF:开放最短路径优先 102 10.7 BGP:边界网关协议 103 10.8 CIDR:无类型域间选路 104 10.9 小结 105 第11章 UDP:用户数据报协议 107 11.1 引言 107 11.2 UDP首部 107 11.3 UDP检验和 108 11.3.1 tcpdump...
10.6 OSPF:开放最短路径优先 102 10.7 BGP:边界网关协议 103 10.8 CIDR:无类型域间选路 104 10.9 小结 105 第11章 UDP:用户数据报协议 107 11.1 引言 107 11.2 UDP首部 107 11.3 UDP检验和 108 11.3.1 tcpdump...
10.6 OSPF:开放最短路径优先 102 10.7 BGP:边界网关协议 103 10.8 CIDR:无类型域间选路 104 10.9 小结 105 第11章 UDP:用户数据报协议 107 11.1 引言 107 11.2 UDP首部 107 11.3 UDP检验和 108 11.3.1 tcpdump...