C++贪心算法单源最短路径问题——Dijkstra算法

问题描述

给定一个带权有向图G=(V,E),其中每条边的权是非负实数。另外，给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路径长度。这里的路长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

算法基本思想

Dijkstra算法是解决单源最短路径问题的一个贪心算法，其基本思想是，设置顶点集合S，并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。
设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短路径长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中的顶点，dist就记录了从源到所有其他顶点之间的最短路径。(注意dist表示的都是源到顶点的最短距离)
算法描述如下:
输入的带权有向图是G=(V,E)，V={1,2…,n}，顶点v是源。c是一个二维数组，c[i][j]表示边(i,j)的权，当(i,j)不属于E时，c[i][j]是一个大数maxint.dist[j]表示当前从源到顶点j的最短路径长度。

代码

#include <iostream>using namespace std;//这里先利用模板类来指定,因为数据类型不固定
template<class Type>
void Dijkstra(int n,int v,Type dist[],int prev[],Type **c){    
//n:图中顶点个数,v:源结点,dist:从源结点出发到各个顶点的距离,prev:通过最短路径到当前结点的上一结点    //c:一个二维数组,用来存储各个边之间的权重    
	bool s[maxint];//用来标识某一结点是否已经进入了我们的集合S(存在于最短路径中的点都存在于S中)    
	for(int i = 1;i <= n;i++)    
	{        
		dist[i] = c[v][i];//初始化源到各点距离,如果不直通就设为maxint        
		s[i] = false;        
		if(dist[i] == maxint)            
			prev[i] = 0;//不连通时前序结点设为0        
		else            
			prev[i] = v;    
	}    
	dist[v] = 0;   
	s[v] = true;    
	for(int i = 1;i < n;i++)    
	{        
		int temp = maxint;        
		int u = v;        
		for(int j = 1;j <= n;j++)        
		{            
		//通过最外层循环,我不断找到当前未加入S中的结点距源节点距离最小的点,将其连入路径中            
			if((!s[j]) && (dist[j]) < temp)            
			{                
				u = j;                
				temp = dist[j];           
			}        
		}        
		s[u] = true;//u结点也被纳入S集合,接下来的点可以计算和u的距离,从而计算到v的距离        
		for(int j = 1;j <= n;j++)        
		{            
			if((!s[j]) && c[u][j] < maxint)            
			{                
				Type newdist = dist[u] + c[u][j];                
				if(newdist < dist[j])                
				{                    
					dist[j] = newdist;                    
					prev[j] = u;                
				}            
			}        
		}    
	}
}

下图就是这个迭代的过程:

如果我们想要直到具体路径就可以利用我们的prev数组，prev[i]存放的就是最短路径中i前面的一个结点。初始化时，对于所有i≠1的点，prev[i]=v。

算法的正确性

我们之前谈论贪心算法的说明过，贪心算法虽然是一个有效的方法，但是它不总是正确的，有可能真的会获得局部最优解。所以我们需要证明它具有最优子结构性质和贪心选择性质。
1.贪心选择性质
Dijkstra算法是应用贪心算法设计策略的又一个典型的例子，所作的贪心选择是从 V-S中选择具有最短特殊路径的顶点u，从而确定从源到u的最短路径长度dist[u]。
但是为什么这个方法会取得最优解呢？
如果存在一条从源到u且长度比dist[u]更短的路，设这条路初次走出S之外到达的顶点为x属于V-S，然后徘徊在S内外若干次，最后离开S到达u。
如图所示：

在这条路径上，分别记d(v,x),d(x,u),d(v,u)为顶点v到顶点x，顶点x到顶点u和顶点v到顶点u的路长，那么，dist[x]<=d(v,x),d(v,x)+d(x,u)=d(v,u)<dist[u]。利用边权的非负性，可知d(x,u)>=0,从而推出dist[x]<dist[u]。但是我们每次都会先选不在S中的顶点距离源v距离最近的顶点作为第一个直接相连的点，所以一开始一定是有dist[u] < dist[x]的，所以此为矛盾。因此dist[u]是从源到顶点u的最短路径长度
2.最优子结构性质
我们的S集合不断地在扩充，先加入的顶点i，dist[i]一定比在S外的所有顶点距离源都小。所以当我们新加入一个顶点进入S时，从源v出发的路径可能会发生一些变化，可能会连接到我们新加入的顶点上然后再连接过去。所以我们的问题一定涉及到前一状态的距离，因为我们需要比较这条新路径和旧路径的长度大小。但是由于先加入的顶点一定比后加入的顶点距离源更近，所以我们的更新比较一般会保留原路径。

总结

外层主循环执行n-1次，内层循环执行n次，所以完成循环需要O(n^2)的时间复杂度。