Dijkstra算法java实现

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

算法描述

　　(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)
　　1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边)
　　2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3
　　3． 对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i), d(j)+Wj->i}，转2
　　Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
　　算法具体步骤　
　　（1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或 ）（若u不是v的出边邻接点）。
　　（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
　　（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
　　（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
编辑本段
复杂度分析

　　Dijkstra 算法的时间复杂度为O(n^2)
　　空间复杂度取决于存储方式，邻接矩阵为O(n^2)

百度百科上有它的c语言实现可以去参考，这里用的是java语言来实现

/**
 * Kuffner提出的算法，即使用Dijkstra算法在栅格中进行路径规划，
 * 利用栅格的特点及栅格中最短路径的特点，对Dijkstra算法进行改进
 * 直交节点只需要扩展时只需要考虑三个邻近节点，
 * 斜交节点扩展时需要考虑五个节点，
 * 所以利用栅格的特点，在扩展邻近节点时，Dijkstra算法的效率提高了百分之五十
**/

package page;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

/**
 * Kuffner类，Kuffner算法的主类部分
 **/
public class BasicDijkstra extends JFrame
{
	public static int MaxM=50;  //环境图中的最大行数
	public static int MaxN=50;  //最大列数
	public static int startx=25;    //开始节点的X值
	public static int starty=25;    //开始节点的Y值
	public static int goalx=38;     //目标节点的X值
	public static int goaly=38;      //目标节点的Y值
	
	private JPanel contentPane;    
	JButton b[][]=new JButton[MaxM][MaxN];   //创建xx*yy个JButton的引用对象，和一个b引用对象指向该数组的第一个位置
	int environ[][]=new int[MaxM][MaxN];     //用于一个整型数组保存环境信息	

	//构造函数，给出环境信息
	public BasicDijkstra()
	{
		super("BasicDijkstra  Method");   

		contentPane=(JPanel)this.getContentPane(); //获得JFrame的内容窗格
		GridLayout layout=new GridLayout(MaxM,MaxN);   //构造一个新的布局管理器layout
		contentPane.setLayout(layout);  //将内容窗格的布局管理器设为GridLayout类型

		//创建并设置按钮组的属性
		new CreatArrayForAll(b,environ,contentPane,MaxM,MaxN,startx,starty,goalx,goaly);

		//调用NDijkstra进行路径规划
		new BDijkstra(b,environ,MaxM,MaxN,startx,starty,goalx, goaly);		

	}

	//主函数部分
	public static void main(String args[])
	{
		BasicDijkstra app=new BasicDijkstra();
		app.setSize(300,300);
		app.show();
		app.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	}
}

/**
 *  根据单元格的坐标在链表中找到该单元格对应的节点
**/

package page;

import java.util.*;

public class BChooseClosed 
{
	public BNodes result=new BNodes();

	//无参构造函数
	public BChooseClosed()
	{
	}

	//有参构造函数，需要给定链表名和坐标值
	public BChooseClosed(LinkedList closed, int x,int y)
	{
		if(closed.size()>0)
		{
			int position=0;
			result=(BNodes)closed.get(position);
			int nowx=result.getX();
			int nowy=result.getY();

			while(nowx!=x||nowy!=y)
			{
				position++;
				if(position<closed.size())
				{
					result=(BNodes)closed.get(position);
					nowx=result.getX();
					nowy=result.getY();
				}
				else
				{
					result=null;
					break;
				}
			}	
		}
		else
			result=null;	
	}

	public BNodes getNode()
	{
		return result;
	}
}

/**
 * Kuffner提出的算法中，选择open表中到起始节点距离最短的节点，
 * now为该节点的引用，
 * position是该节点在open表中的位置
**/

package page;

import java.util.*;

public class BChooseOpen 
{
	public BNodes now=new BNodes();
	
	public  BChooseOpen()
	{
	}
	
	public BChooseOpen(LinkedList open)
	{
		if(open.size()>0)
		{	
			now=(BNodes)open.get(0);
			int nowdis=now.getDistance();  //now节点到初始节点的距离
		
			BNodes result=new BNodes();
			int resdis=0;
	
			for(int i=1;i<open.size();i++)
			{
				result=(BNodes)open.get(i);
				resdis=result.getDistance();
				if(resdis<nowdis)
				{
					now=result;
					nowdis=now.getDistance();
				}
			}
		}
		else
			now=null;
	}

	public BNodes getNode()
	{
		return now;
	}
}

/**
 * 使用改进的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)
	}//构造函数
}//类定义

/**
 * 该类的功能是在Kuffner算法中，判断某节点的一个临近单元格是否扩展过，
 * 如果没有扩展过，则对其进行扩展，创建对应的节点并加入open表中
 * 如果已经扩展过，而该临近节点与该节点的关系是直交，则需要对其对应节点
 * 的距离长度进行判断，如果该长度大于从目前节点扩展到该节点的长度，
 * 则对该单元格对应的节点的属性进行更改
**/

package page;

import java.util.*;

public class BExtendDemo 
{
	public BExtendDemo ()
	{
	}	
		
	//对斜交子单元格的判定
	public BExtendDemo (int[][] environ,int x,int y,int distance2,LinkedList open,int nowx,int nowy)
	{
		if(environ[x][y]==0)   //如果为零，则说明该单元格可达，而且没有扩展过
		{
			environ[x][y]=distance2;    //在数组中显示该节点的路径长度					
			open.add(new BNodes(x,y,nowx,nowy,distance2));
		}	
	}

	//对直交子单元格的判定
	public BExtendDemo (int[][] environ,int x,int y,int distance1,LinkedList open,int nowx,int nowy,int i)
	{
		if(environ[x][y]==0)  //如果为零，则说明该单元格可达，而且没有扩展过
		{
			environ[x][y]=distance1;    //在数组中显示该节点的路径长度
			open.add(new BNodes(x,y,nowx,nowy,distance1));			
		}
		
		//不为零且是可达单元，说明之前已经扩展过，那么只需要对其距离进行比较处理即可	
		else if(environ[x][y]!=555)  
		{
			//如果其距离长度大于distance1，则从open表中找出该节点，对其属性进行更改
			if(environ[x][y]>distance1)
			{
				if(open.size()>0)
				{
					environ[x][y]=distance1;
					
					BNodes now=(BNodes)new BChooseClosed(open,x,y).getNode();
					now.setPre(nowx,nowy);
					now.setDistance(distance1);
				}
			}
		}
	}//构造函数结束
}

/**
 * KNnodes类，用于定义每个节点，类似于C语言中的结构体
 * 该类中的变量有：节点的坐标，其父节点的坐标，从该节点到初始节点的最短距离
 * 该类中的方法有：无参构造函数（该节点坐标为0，0父节点坐标为-1，-1，距离长度为555）
 * 有参构造函数，给定所有的参数；设置、获得坐标值、父节点坐标值、 距离值
**/

package page;

public class BNodes
{
	int nodex;     //节点的x值
	int nodey;     //节点的y值
	int prex;      //父节点的x值
	int prey;      //父节点的y值
	int distance;  //从初始节点到该节点的最短距离	

	//无参构造函数
	public BNodes()
	{
		nodex=0;
		nodey=0;		
		prex=-1;
		prey=-1;
		distance=555;
	}

	//有参构造函数
	public BNodes(int x,int y,int preX,int preY,int dis)   
	{
		nodex=x;
		nodey=y;		
		prex=preX;
		prey=preY;
		distance=dis;
	}

	public int getX()      //获得该节点的X值
	{
		return nodex;
	}

	public int getY()      //获得该节点的Y值
	{
		return nodey;
	}

	public void setPre(int x,int y)   //设置父节点的x、y值
	{
		prex=x;
		prey=y;
	}

	public int getPrex()   //获得父节点的x值
	{
		return prex;
	}

	public int getPrey()   //获得父节点的y值
	{
		return prey;
	}
	
	public void setDistance(int d)    //设置节点的路径长度
	{
		distance=d;
	}

	public int getDistance()        //获得节点的路径长度
	{
		return distance;
	}
}

/**
* CreatArrayForAll类用于初始化数组，可为各种算法所使用
* 给定JButton和int类型的数组及一个Jpanel变量，
* 给定环境的大小(x,y)和初始位置及目标位置
*
**/

package page;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class CreatArrayForAll  
{
	public CreatArrayForAll()
	{
	}

	public CreatArrayForAll(JButton[][] b,int[][] environ,JPanel contentPane,int MaxM,int MaxN,int startX,int startY,int goalX,int goalY)
	{
		int i=0;
		//初始化环境图：创建并设置按钮组的属性，所有的按钮背景为白，前台颜色为黑，数组所有元素为零
		for( i=0;i<MaxM;i++)
		{
			for(int j=0;j<MaxN;j++)
			{
				//创建一个按钮，并将按钮加入窗体中
				b[i][j]=new JButton();
				b[i][j].setBackground(Color.white);  //背景颜色为白色
				b[i][j].setForeground(Color.black);  //前台颜色为黑色
				contentPane.add(b[i][j]); 

				environ[i][j]=0;  
			}
		}

	    //设置障碍区域颜色为黑色，environ数组中的值设为555
	    b[4][42].setBackground(Color.black); 	environ[4][42]=555;
	    b[4][43].setBackground(Color.black);	environ[4][43]=555;
	    b[5][43].setBackground(Color.black);	environ[5][43]=555;
	    b[5][44].setBackground(Color.black);	environ[5][44]=555;
	    b[6][43].setBackground(Color.black);	environ[6][43]=555;
	    b[6][44].setBackground(Color.black);	environ[6][44]=555;
	    b[7][44].setBackground(Color.black);	environ[7][44]=555;
	    b[7][45].setBackground(Color.black);	environ[7][45]=555;
	    b[8][46].setBackground(Color.black);	environ[8][46]=555;
	    b[8][47].setBackground(Color.black);	environ[8][47]=555;
	    b[8][28].setBackground(Color.black);	environ[8][28]=555;
	    b[8][29].setBackground(Color.black);	environ[8][29]=555;
	    b[9][28].setBackground(Color.black);	environ[9][28]=555;
	    b[9][29].setBackground(Color.black);	environ[9][29]=555;
	    b[10][9].setBackground(Color.black);	environ[10][9]=555;
	    b[11][8].setBackground(Color.black);	environ[11][8]=555;
	    b[11][9].setBackground(Color.black);	environ[11][9]=555;
	    b[11][30].setBackground(Color.black);	environ[11][30]=555;
	    b[12][29].setBackground(Color.black);	environ[12][29]=555;
	    b[12][30].setBackground(Color.black);	environ[12][30]=555;
	    for(i=7;i<=11;i++)
	    {
	    	b[13][i].setBackground(Color.black);	environ[13][i]=555;
	    	b[18][i].setBackground(Color.black);	environ[18][i]=555;
	    }
		for(i=28;i<=31;i++)
		{
			b[13][i].setBackground(Color.black);	environ[13][i]=555;
	    	b[14][i].setBackground(Color.black);	environ[14][i]=555;
		}
		b[22][49].setBackground(Color.black);	environ[22][49]=555;
		b[23][48].setBackground(Color.black);	environ[23][48]=555;
		b[23][49].setBackground(Color.black);	environ[23][49]=555;
		for(i=47;i<50;i++)
		{
			b[24][i].setBackground(Color.black);
			environ[24][i]=555;			
		}
		b[24][9].setBackground(Color.black);	environ[24][9]=555;
		b[23][8].setBackground(Color.black);	environ[23][8]=555;
		b[23][9].setBackground(Color.black);	environ[23][9]=555;
		b[25][48].setBackground(Color.black);	environ[25][48]=555;
		b[25][49].setBackground(Color.black);	environ[25][49]=555;
		b[26][49].setBackground(Color.black);	environ[26][49]=555;
		
		b[49][28].setBackground(Color.black);	environ[49][28]=555;
		for(i=32;i<=33;i++)
		{
			b[14][i].setBackground(Color.black);
			environ[14][i]=555;
			b[15][i].setBackground(Color.black);
			environ[15][i]=555;
		}
		b[48][28].setBackground(Color.black);	environ[48][28]=555;
		for(i=27;i<30;i++)
		{
			b[49][i].setBackground(Color.black);
			environ[49][i]=555;			
		}
		
		b[42][8].setBackground(Color.black);	environ[42][8]=555;
		b[42][9].setBackground(Color.black);	environ[42][9]=555;
		b[42][25].setBackground(Color.black);	environ[42][25]=555;
		b[42][26].setBackground(Color.black);	environ[42][26]=555;
		b[42][42].setBackground(Color.black);	environ[42][42]=555;
		b[42][43].setBackground(Color.black);	environ[42][43]=555;
		b[43][9].setBackground(Color.black);	environ[43][9]=555;
		b[43][42].setBackground(Color.black);	environ[43][42]=555;
		b[44][13].setBackground(Color.black);	environ[44][13]=555;
		b[46][13].setBackground(Color.black);	environ[46][13]=555;
		for(i=12;i<15;i++)
		{
			b[45][i].setBackground(Color.black);
			environ[45][i]=555;			
		}

		//将初始单元格和目标单元格标记出来
	//	b[startX][startY].setText("Start");
	//	b[goalX][goalY].setText("Goal");
		b[startX][startY].setBackground(Color.red);
		b[goalX][goalY].setBackground(Color.red);
	}
}

评论

1 楼 alfredgao 2014-09-30  

lz的运行界面是怎样的？