bdijkstra.java

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

/**
 * 使用改进的Dijkstra算法进行路径规划，每次选出一个到初始节点距离最短的节点
 *
**/


package page;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;       //LinkedList

public class BDijkstra 
{
	public static int comparenumber=0;    //用于保存该算法所进行的比较次数
	
	//无参构造函数
	public  BDijkstra()
	{		
	}
	
	//有参构造函数
	public  BDijkstra(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表中，该节点的父节点指向自身
			BNodes now=new BNodes(startX,startY,startX,startY,0);		
			closed.add(now);
			comparenumber++;

			nowx=startX;
			nowy=startY;
			nowdis=0;

			int x=nowx-1;   //目前正在处理的单元的邻近单元位置
			int y=0; 
			int distance1=nowdis+10;  //目前正在处理单元的邻近单元到初始节点的距离
			int distance2=nowdis+14;

			//求出算法开始时间
			double h1=new java.util.Date().getTime();
			
			//规划到目标节点之前执行如下循环
			while(nowx!=goalX||nowy!=goalY)
			{
				//处理上一行的三个邻近单元	
				if(x>=0&&x<MaxM)  //如果上一行存在，则对其上一行的邻近节点进行判断
				{
					y=nowy-1;	
					if(y>=0&&y<MaxN)  //如果该节点存在
					{
						comparenumber++;
						new BExtendDemo (environ,x,y,distance2,open,nowx,nowy);
					}
					y=nowy;
					comparenumber++;
					new BExtendDemo (environ,x,y,distance1,open,nowx,nowy);	
					y=nowy+1;	
					if(y>=0&&y<MaxN)  //如果该节点存在
					{
						comparenumber++;
						new BExtendDemo (environ,x,y,distance2,open,nowx,nowy);
					}
				}
				
				//处理同一行的两个节点
				x=nowx;			
				y=nowy-1;
				if(y>=0&&y<MaxN)  //如果该节点存在
				{
					comparenumber++;
					new BExtendDemo (environ,x,y,distance1,open,nowx,nowy);
				}
				y=nowy+1;
				if(y>=0&&y<MaxN)  //如果该节点存在
				{
					comparenumber++;
					new BExtendDemo (environ,x,y,distance1,open,nowx,nowy);
				}
				
				//处理下一行的三个邻近节点
				x=nowx+1;
				if(x>=0&&x<MaxM)  //如果下一行存在，则对其上一行的邻近节点进行判断
				{
					y=nowy-1;	
					if(y>=0&&y<MaxN)  //如果该节点存在
					{
						comparenumber++;
						new BExtendDemo (environ,x,y,distance2,open,nowx,nowy);
					}
					y=nowy;
					comparenumber++;
					new BExtendDemo (environ,x,y,distance1,open,nowx,nowy);	
					y=nowy+1;	
					if(y>=0&&y<MaxN)  //如果该节点存在
					{
						comparenumber++;
						new BExtendDemo (environ,x,y,distance2,open,nowx,nowy);
					}
				}				
				
				//选出open表中路径最短者
			    now=(BNodes)new BChooseOpen(open).getNode();
			    nowx=now.getX();     
				nowy=now.getY();
				nowdis=now.getDistance();				
				distance1=nowdis+10;  //目前正在处理单元的邻近单元到初始节点的距离
				distance2=nowdis+14;
				x=nowx-1;
				y=nowy;
				
				b[nowx][nowy].setText(""+environ[nowx][nowy]);
								
				open.remove(now);
				closed.add(now);
			}

			double h2=new java.util.Date().getTime();
			System.out.println("该程序的运行时间为： "+(h2-h1)+"  毫秒");

			/*for(int i=0;i<20;i++)
			{
				for(int j=0;j<20;j++)
					System.out.print("	"+b[i][j].getText());
				System.out.println();
			}	*/
						
		
			System.out.println("the number of the planned nodes  is: "+closed.size());
			System.out.println("the number of the extended nodes is: "+(open.size()+closed.size()));
			System.out.println("the number of the considered nodes is:   "+comparenumber);

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