贪心算法与数据结构结合1——单源最短路径问题：Dijkstra算法

万众一心，共同抗击灾难。这是我们国家自古以来的美德
国家遭受重大灾情，每个中国人都是有义务去解决这样的重大问题。
国家紧紧和老百姓拴在一起，凝聚着中国魂，中国力量，中国精神！

数据结构中的有一个图论问题——单源最短路径问题，而解决这一问题的算法是Dijkstra算法。而本篇主要介绍单源最短路径问题和Dijkstra算法

1、单源最短路径问题

什么是单源最短路径问题

给定带权有向网络G=(V,E,W),每条边e=<i,j>的权w(e)为非负实数，表示从i到j的距离。源点s属于V
求：从s出发到达其他结点的最短路径
例如这个图

我们以源点1出发寻找到达其他结点的最短路径
我们从1出发1->6->2是结点1到结点2的最短路径，这个路径的长度是3+2=5
我们从1出发1->6->2->3是结点1到结点3的最短路径，这个路径的长度是3+2+7=12
我们从1出发1->6->4是结点1到结点4的最短路径，这个路径的长度是3+6=9
我们从1出发1->6->5是结点1到结点5的最短路径，这个路径的长度是3+1=4
我们从1出发1->6是结点1到结点6的最短路径，这个路径的长度是3

那么如何找到这个最短路径呢
我们可以用贪心法来找最短路径
这个贪心法就是著名的Dijkstra算法
下面我们来看一下Dijkstra算法

2、Dijkstra算法

什么是Dijkstra算法

Dijkstra算法是解决图论中单源最短路径问题的算法
把顶点集合V分成两组：
（1）S：已求出的顶点的集合（初始时只含有源点V0）
（2）V-S：尚未确定的顶点集合

在G={V,E}中
1、初始时令 S={V0},V-S={其余顶点}，T中顶点对应的距离值；若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值；若不存在<V0,Vi>，d(V0,Vi)为∞

2、从V-S中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中

3、对其余V-S中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

4、重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

下面我们对算法举个例子：
我们还是对上面那个问题进行分析

我们把源点1选到S集合里面，而V-S={2,3,4,5,6}
选完之后就要实时更新边
这里dist[i]:从w到i相对S最短路径长度

我们看到啊
源点1到源点1的长度为0
源点1到源点2的长度为10
源点1到源点6的长度为3
而源点1到3，4，5是不可到达的，也就是没有有向线段是从源点1出发指向3，4，5的。故它们的长度是正无穷

接下来我们就在所更新的边（dist数组）里面找到一个长度最小的值，我们看到dist[6]长度最小
然后把源点6选到S集合里
那么S={1，6},V-S={2,3,4,5}
我们看到啊，在源点6进到集合里后，其他点的最短路，可以经过源点6。那么路线可能会被更新

这里，源点1可以经过源点6到源点2，即1->6->2，最短路径长度被更新为3+2=5
源点1可以经过源点6到源点2，即1->6->2，最短路径长度被更新为3+2=5
源点1可以经过源点6到源点4，即1->6->4，最短路径长度被更新为3+6=9
源点1可以经过源点6到源点2，即1->6->5，最短路径长度被更新为3+1=4
而还是没有一条有向线段经过源点3，故dist[3]=∞

然后再在所更新的边里面找到剩下的一个长度最小的值，我们看到dist[5]长度最小
于是把源点5选到S集合里
然后再计算并更新边

再将源点2选进去
然后再更新边

我们此时看到源点2有一条有向线段经过源点3，更新路径dist[3]=12
dist[4]长度最小
于是把源点4选到集合S里
然后更新边

最后将源点3选到S集合里去，那个这个图和旁边的最短路径就是原问题的解

如何说明这个算法是正确的呢，下面我们用数学归纳法进行证明

数学归纳法证明Dijkstra算法

我们有一个命题：当算法进行到第k步时，对于S中每个结点i，有dist[i]=short[i]
首先对于k=1时，S={s},只有一个点的时候，没有有向边。因此只有一个点的时候，其最短路是0，dist[s]=short[s]=0，显然归纳基础成立。

假设命题对k为真，下面证明对k+1也为真
也就是证明在k+1步算法中，选择顶点v，需要证明dist[v]=short[v]
如若不然，存在另一条s-v路径的一个最短路径L

这个路径L是图中绿色的路线，最后一次出S集合的顶点last_point，经过V-S的第一个顶点y，再有y经过一段在V-S中的路径到达v。

在k+1步中选择顶点v时，上面是假设路线，下面是算法选择的路线
我们看到last_point是不能和顶点v相连，因为在k+1步时，算法选择了一条最短路线，在S集合里的u指向了S集合外的v；所以如果last_point直接和v相连，此时L必然>=dist[v]，不是最短路径。所以last_point要经过多点与v相连，从而找到一条最短路径。

如果last_point与y点相连，在k+1步时，算法选择了v点而不是y点，所以dist[v]<=dist[y]。
令y到v的路径长度为d(y,v)
因此有dist[y]+d(y,v)=L=dist[v]=short[v]
而又因为dist[v]<=dist[y],dist[y]<=L
所以dist[v]<=L。这与L=dist[v]矛盾。所以不存在一个相对算法更小的最短路径L，故Dijkstra算法是正确的。因此，得证。

下面分析Dijkstra算法的代码
我们将选好的点集存放在数组里，定义一个图集类的变量存放边或者进行更新边的操作。首先进行初始化，将源点1加进去，并将1到各点的边的数值加到图集类的变量中去（这个变量也是个数组），然后遍历图集类数组变量，如果找到一条最短的边，则把下标记下来，便于进行下一步寻找最短边和更新边操作以及求解。然而更新边操作，我们找到了一个最短边相连的点，将这个点也加到了集合里去了，再判断这个点和其他边+上一个求得最小边小于原始的边，则进行更新。可能看起来有点绕，一会可以从代码中体会

下面上代码

public class Graph {
	int v1;  //v1顶点
	int v2;  //v2顶点
	int len;  //权值
	
	public Graph() {
		// TODO Auto-generated constructor stub
	}

	public Graph(int v1, int v2, int len) {
		super();
		this.v1 = v1;
		this.v2 = v2;
		this.len = len;
	}
	
	
}

public static void main(String[] args) {
		// TODO Auto-generated method stub
		//设置权重：自己和自己连的是0，没有边的是-1，其他的都是自己权重值
				int[][] a = {
		                {0,10,-1,-1,-1,3},
		                {-1,0,7,5,-1,-1},
		                {-1,-1,0,-1,-1,-1},
		                {3,-1,4,0,7,-1},
		                {-1,-1,-1,-1,0,-1},
		                {-1,2,-1,6,1,0}
		        };
				
				CreateGraph(a, a.length);
				
				MinPath(a);
	}
	
	//创建图
	public static void CreateGraph(int a[][],int m) {
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				if(a[i][j]==-1||a[i][j]==0)
					a[i][j]=0x3f3f3f3f;
	}
	
	//贪心算法解单源最短路径问题
	public static void MinPath(int a[][]) {
		int k=0;  //表示正在访问的点
		int min=0;
		int pointWeight[]=new int[a.length];  //记录权值
		int numPoint=a.length;
		Boolean p[]=new Boolean[a.length];  //判断哪些点已经被取到了
		Graph minWeight[]=new Graph[a.length];  
		Graph tracing[]=new Graph[a.length];  //单源最短路径问题的解
		
		minWeight[0]=new Graph(0, 0, a[0][0]);
		p[0]=true;
		for(int i=1;i<a.length;i++) {
			minWeight[i]=new Graph(0,i,a[0][i]);
			p[i]=false;
		}
		
		for(int i=1;i<a.length;i++) {
			min=0x3f3f3f3f;
			for(int j=0;j<a.length;j++)
				if(!p[j]&&minWeight[j].len<min) {
					min=minWeight[j].len;
					k=j;
				}
			
			p[k]=true;  //找到一个最小权值的点
			tracing[i-1]=minWeight[k];
			pointWeight[k]=min;
			numPoint--;
			//更新当前最短路径
			for(int j=0;j<a.length;j++) {
				if(!p[j]&&(min+a[k][j])<minWeight[j].len) {
					minWeight[j]=new Graph(k,j,min+a[k][j]);
				}
			}
		}
		if(numPoint==1)
			TracingMixPath(tracing, pointWeight);
		else
			System.out.println("没有最短路径");
	}
	
	//遍寻单源最短路径
	public static void TracingMixPath(Graph tracing[],int pointWeight[]) {
		System.out.println("可连接的最短路径：");
		for(int i=0;i<tracing.length-1;i++) 
	    	System.out.println((tracing[i].v1+1)+"-->"+(tracing[i].v2+1)+"          ");
		
		System.out.println("此时最短路径的长度分别是：");
		for(int i=0;i<pointWeight.length;i++)
			System.out.println("short["+(i+1)+"]="+pointWeight[i]);
	}

下面分析Dijkstra算法

分析Dijkstra算法

代码采用了带权邻接矩阵进行分析的，所以说时间复杂度就是O(n^2)
我们看下代码，在第一个for循环是遍寻所有点，第二个for循环是找到最小边，在第二个for循环出来之后才有了第三个for循环，这个循环是更新边
所以时间复杂度也是O(n^2)

综上Dijkstra算法的时间复杂度就是O(n^2)

如果采用了基于堆实现的优先队列的数据结构，可以将算法时间复杂度降到O(nlogn)
对于这个的实现，大家可以自己研究下。这里就不再详细介绍了

######          积力之所举，则无不胜也；众智之所为，则无不成也。（刘安《淮南子·主术训》）