欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-17 08:39:34
...

问题描述

给定一个带权有向图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;                
				}            
			}        
		}    
	}
}

下图就是这个迭代的过程:
C++贪心算法单源最短路径问题——Dijkstra算法
如果我们想要直到具体路径就可以利用我们的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。
如图所示:
C++贪心算法单源最短路径问题——Dijkstra算法
在这条路径上,分别记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)的时间复杂度。

相关标签: 贪心算法