最短路径Dijkstra算法 java

墨蓝 2021-09-25 23:34 479阅读 0赞

思路：设置一个基点集合 S ，并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设 u 是 G 的某一个顶点，我们把从源到 u 且中间只有经过 S 中顶点的路称为从源到 u 的特殊路径，并且数组 dist 来记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从 V-S 中取出具有最短特殊路径长度的项点 u ，将 u 添加到 S 中，同时对数组 dist 作必要的修改。

![20160719222449116][]

举例A到各点的最短举例：

首先，初始化A到各点的直接距离，没有直接距离的用MAX表示。

此时dist\[\]：

AàD=7

步骤1：

得到AàC=2时最小值，把C下标纳入S集合中，此时dist\[\]

C对其他非S集合中的且有直接距离的元素进行更新距离，此时dist\[\]：

CàB=4+2>3，CàD=2+2<7(更新),CàE=3+2<MAX(更新)，CàF=5+2<MAX(更新)

步骤2：

得到A àB=3是最小值，把B纳入S集合中，此时dist\[\]：

B对其他非S集合中的且有直接距离的元素进行更新距离，此时dist\[\]：

BàE=6+3 (AB)>5,，

步骤3：

得到ACàD=4为最小值，把D纳入集合S中，此时dist\[\]：

D对其他非S集合中的且有直接距离的元素进行更新距离，此时dist\[\]：

DàF=1+4=5<7(ACF)(更新)

步骤4：

得到ACàE=5为最小值，把E纳入集合S中，此时dist\[\]：

E对其他非S集合中的且有直接距离的元素进行更新距离，此时dist\[\]：

EàF=2+5=7>5，

步骤5：

得到ACDàF=5为最小值，把F纳入集合S中，此时dist\[\]：

没有剩余的元素，结束。

代码：

public class Dijkstra {
 	final static int N=6;
 	final static int MAX=100;
 	public static void Dij(int[][] g,int source)
 	{
 		//定义dist数组来记录距离。
 		//定义boolean 型S数组记录是否计算过该点
 		int[] dist=new int[N];
 		boolean[] S=new boolean[N];
 		
 		//初始化dist[]和S[]
 		for(int i=0;i<N;i++)
 		{
 			S[i]=false;
 			dist[i]=(g[source][i]==0?MAX:g[source][i]);
 		}
 		
 		//把source纳入S[]区间,自己到自己的距离为0。
 		S[source]=true;
 		dist[source]=0;
 		
 		//source已经知道，剩下的就只有N-1次，用count记录
 		for(int count=1;count<N;count++)
 		{
 			int u=-1;
 			int min=MAX;
 			//在S集合外寻找u，即距离最短的点的下标。
 			for(int j=0;j<N;j++)
 			{
 				
 				if(dist[j]<min && !S[j])
 				{
 					min=dist[j];
 					u=j;
 				}
 			}
 			//u加入到S集合中
 			S[u]=true;
 			
 			for(int i=0;i<N;i++)
 			{
 				if(u==-1)//当且仅当没有任何路径到i点时，不用计算距离了，直接跳出。
 					break;
 				if(!S[i] && g[u][i]!=0 && dist[u]!=MAX && dist[u]+g[u][i]<dist[i])
 				{
 					dist[i]=dist[u]+g[u][i];
 				}
 			}
 		}
 		
 		PrintDist(dist,source);
 	}
 	
 	//打印最短距离
 	public static void PrintDist(int[] dist,int source)
 	{
 		for(int i=0;i<N;i++)
 		{
 			System.out.println(source+"到"+i+"的最短距离为："+dist[i]);
 		}
 	}
 	
 	public static void main(String[] args)
 	{
 		int[][] graph={
 				{0,3,2,7,0,0},
 				{3,0,4,0,6,0},
 				{2,4,0,2,3,5},
 				{7,0,2,0,0,1},
 				{0,6,3,0,0,2},
 				{0,0,5,1,2,0}	
 				
 			/*	{ 0, 4, 0, 0, 0, 0, 0, 8, 0 }, 
 				{ 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
 				{0, 8, 0, 7, 0, 4, 0, 0, 2 },
 				{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
 				{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
 				{ 0, 0, 4, 0, 10, 0, 2, 0, 0 },
 				{ 0, 0, 0, 14, 0, 2, 0, 1, 6 },
 				{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
 				{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }*/
 		};
 		Dij(graph,0);//0表示求原始点到各点的距离
 	}
 }

结果：

0到0的最短距离为：0  
0到1的最短距离为：3  
0到2的最短距离为：2  
0到3的最短距离为：4  
0到4的最短距离为：5  
0到5的最短距离为：5

[20160719222449116]: /images/20210923/98969a72fb98453f898b80c59a088458.png