BDijkstra算法的java实现 使用工具是eclipse，java1.4以上.zip

/** * 使用改进的Dijkstra算法进行路径规划，每次选出一个到初始节点距离最短的节点 * **/ package page; import java.awt.*; import java.awt.event.*; import javax.swing.*; import java.util.*; //LinkedList public class KDijkstra { public static int comparenumber=0; //用于保存该算法所进行的比较次数 public static int computernumber=0; //用于计算该算法进行计算的次数 //无参构造函数 public KDijkstra() { } //有参构造函数 public KDijkstra(JButton[][] b,int[][] environ,int MaxM,int MaxN,int startX,int startY,int goalX,int goalY) { //如果目标位置就是初始位置，则直接输出说明语句即可，无需进行路径规划。 if(startX==goalX&&startY==goalY) { System.out.println("the goal cell is the start cell, so do not need to planning path!"); } //如果目标位置不是初始位置，则进行如下的路径规划 else { //给出算法所用变量的说明 LinkedList open=new LinkedList(); //保存扩展到的节点 LinkedList closed=new LinkedList(); //保存规划过的节点 int nowx=0,nowy=0; //目前正在处理单元格的位置 int nowdis=0; //目前正在处理单元格到初始单元格的距离 //处理初始单元格，创建其对应的节点加入closed表中，该节点的父节点指向自身 KNodes now=new KNodes(startX,startY,startX,startY,0); closed.add(now); nowx=startX; nowy=startY; nowdis=0; int x=nowx-1; //目前正在处理的单元的邻近单元位置 int y=0; int distance1=nowdis+10; //目前正在处理单元的邻近单元到初始节点的距离 int distance2=nowdis+14; //处理初始单元的八个邻近单元，创建其对应的节点，并加入open表中 //处理初始单元格的上一行的三个邻近单元 if(x>=0&&x<MaxM) //如果上一行存在，则对其上一行的邻近节点进行判断 { y=nowy-1; if(y>=0&&y<MaxN) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); y=nowy; new KExtendDemo (environ,x,y,distance1,open,nowx,nowy); y=nowy+1; if(y>=0&&y<MaxN) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); }//上一行的三个邻近单元处理结束 //处理同一行的两个节点 x=nowx; y=nowy-1; if(y>=0&&y<MaxN) new KExtendDemo (environ,x,y,distance1,open,nowx,nowy); y=nowy+1; if(y>=0&&y<MaxN) new KExtendDemo (environ,x,y,distance1,open,nowx,nowy); //同行的两个节点处理完毕 //处理下一行的三个邻近节点 x=nowx+1; if(x>=0&&x<MaxM) //如果下一行存在，则对其下一行的邻近节点进行判断 { y=nowy-1; if(y>=0&&y<MaxN) //如果下左节点存在，则对其进行判断 new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); y=nowy; new KExtendDemo (environ,x,y,distance1,open,nowx,nowy); y=nowy+1; if(y>=0&&y<MaxN) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); }//下一行的三个邻近单元处理结束 //初始节点的八个邻近单元处理完毕 //选出open表中路径最短者 now=(KNodes)new KChooseOpen(open).getNode(); int prex=0; int prey=0; int addx=0; int addy=0; nowx=now.getX(); nowy=now.getY(); //Step4: 判断循环条件，判断是否已经标识了目标节点，如果没有，则进行下面的循环 while(nowx!=goalX||nowy!=goalY) { //Step5: 从open中将距离最短的节点删除,将该节点的临近节点加入open对列中 open.remove(now); closed.add(now); nowdis=now.getDistance(); distance1=nowdis+10; distance2=nowdis+14; prex=now.getPrex(); prey=now.getPrey(); addx=prex-nowx; addy=prey-nowy; //父节点在下面一行 if(addx==1) { if(addy==1)//父节点在右下位置，需要处理的节点有上一行和左一列 { //处理上一行 x=nowx-1; if(x>=0&&x<MaxM) { y=nowy-1; if(y>=0&&y<MaxN) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); y=nowy; new KExtendDemo(environ,x,y,distance1,open,nowx,nowy,0); y=nowy+1; if(y>=0&&y<MaxN) new KExtendDemo(environ,x,y,distance2,open,nowx,nowy); }//上一行处理完毕 //处理左边节点 y=nowy-1; if(y>=0&&y<MaxN) { x=nowx; new KExtendDemo(environ,x,y,distance1,open,nowx,nowy,0); x=nowx+1; if(x>=0&&x<MaxM) new KExtendDemo(environ,x,y,distance2,open,nowx,nowy); }//左边节点处理完毕 }//addx==1&&addy==1 else if(addy==0) { //需要处理上一行节点 x=nowx-1; if(x>=0&&x<MaxM) //如果上一行存在，则对其上一行的邻近节点进行判断 { y=nowy-1; if(y>=0&&y<MaxN) //如果上左节点存在，则对其进行判断 new KExtendDemo(environ,x,y,distance2,open,nowx,nowy); y=nowy; new KExtendDemo(environ,x,y,distance1,open,nowx,nowy,0); y=nowy+1; if(y>=0&&y<MaxN) new KExtendDemo(environ,x,y,distance2,open,nowx,nowy); }//上一行处理完毕 }//addx==1&&addy==0 else//需要处理上一行和右一列 { //上一行 x=nowx-1; if(x>=0&&x<MaxM) { y=nowy-1; if(y>=0&&y<MaxN) new KExtendDemo(environ,x,y,distance2,open,nowx,nowy); y=nowy; new KExtendDemo(environ,x,y,distance1,open,nowx,nowy,0); y=nowy+1; if(y>=0&&y<MaxN) new KExtendDemo(environ,x,y,distance2,open,nowx,nowy); }//上一行处理完毕 //右一列 y=nowy+1; if(y>=0&&y<MaxN) { x=nowx; new KExtendDemo (environ,x,y,distance1,open,nowx,nowy,0); x=nowx+1; if(x>=0&&x<MaxM) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); }//右边节点处理完毕 }//addx==1&&addy==1 } //if(addx==1) 父节点在下一行 //父节点与now节点同行 else if(addx==0) { if(addy==1)//需要处理左一列 { y=nowy-1; if(y>=0&&y<MaxN) { x=nowx-1; if(x>=0&&x<MaxM) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); x=nowx; new KExtendDemo (environ,x,y,distance1,open,nowx,nowy,0); x=nowx+1; if(x>=0&&x<MaxM) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); } }//addx==0&&addy==1 else if(addy==-1)//需要处理右一列 { y=nowy+1; if(y>=0&&y<MaxN) { x=nowx-1; if(x>=0&&x<MaxM) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); x=nowx; new KExtendDemo (environ,x,y,distance1,open,nowx,nowy,0); x=nowx+1; if(x>=0&&x<MaxM) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); } }//addx==0&&addy==-1 }//else if(addx==0) 父节点与子节点在同一行 //父节点在上一行(addx==-1) else { if(addy==1)//父节点在右上位置，需要处理的节点有下一行和左一列 { //处理下一行 x=nowx+1; if(x>=0&&x<MaxM) { y=nowy-1; if(y>=0&&y<MaxN) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); y=nowy; new KExtendDemo (environ,x,y,distance1,open,nowx,nowy,0); y=nowy+1; if(y>=0&&y<MaxN) new KExtendDemo (environ,x,y,distance2,open,nowx,nowy); }//下一行处理完毕 //处理左边节点 y=nowy-1; if(y>=0&&y<MaxN) { x=no