kdijkstra.java

BDijkstra算法的java实现。使用工具是eclipse

/**
 * 使用改进的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=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
				}//父节点在上一行
				//节点处理结束

				//选出open表中路径最短者				
				now=new KChooseOpen(open).getNode();
				nowx=now.getX();     
				nowy=now.getY();

			}//while(nowx!=goalX||nowy!=goalY)

			//将路径经过的节点的颜色改变
			int number=0;
			b[nowx][nowy].setForeground(Color.green);  
			number++;
			
			x=now.getPrex();  
			y=now.getPrey();
			b[x][y].setForeground(Color.green);  
			number++;

			while(x!=startX||y!=startY)
			{			
				now=(KNodes)new KChooseClosed(closed,x,y).getNode();				
				x=now.getPrex();
				y=now.getPrey();
				b[x][y].setForeground(Color.green); 
				number++;
			}
			System.out.println("the number of the nodes in the planned path is:   "+number);
			number=0;
			
			System.out.println("the number of the planned nodes in the process of planning path is: "+closed.size());
			number=open.size()+closed.size();
			System.out.println("the number of the extended nodes in the process of planning path is: "+number);

			//在环境图中显示路径长度
			for(int i=0;i<MaxM;i++)
			{
				for(int j=0;j<MaxN;j++)
				{
					b[i][j].setText(""+environ[i][j]);
				}
			}
			b[startX][startY].setText(""+0);

		}//else==!(startX==goalX&&startY==goalY)
	}//构造函数
}//类定义