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

计算机算法设计与分析 (四) 贪心算法--单源最短路径

程序员文章站 2022-05-23 09:57:59
...

1.Dijkstra算法是解决单源最短路径的一个贪心算法。给定一个带权有向图G=(V,E),其中每条边的权都是非负实数,另外,还给定V中的一个顶点,称为源。现在要计算源到其他各个顶点的最短路长度。这里的路的长度指的是路上各边权之和。
Dijkstra算法可描述如下,其中输入的带权有向图是G=(V,E),顶点v是源。c是一个二维数组,c[i][j]表示边(i,j)的权。当(i,j)之间无直接的边连接时,c[i][j]是一个大数。dist[i]表示当前从源点到顶点i的最短特殊路径长度。

template<class Type>
void Dijkstra(int n, int v,Type dist[][],int prev[],Type **c)
{
	bool s[n+1];
	for(int i=1;i<=n;++i)
	{
		dist[i]=c[v][i];
		s[i]=false;
		if(dist[i]==Int_Max) prev[i]=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 i=1;i<n;i++)
		{
			if(dist[j]<temp&&!s[i])//选出当前剩余点中距离v最近的点
			{
				u=j;
				temp=dist[j];
			}
		}
		s[u]=true
		for(int j=1;j<=n;++j)//更新dist数组
		{
			if(!s[i]&&c[u][j]+dist[u]<dist[j])
			{	
				dist[j]=c[u][j]+dist[u];
				prev[j]=u;
			}
		}
	}
}

算法的正确性和复杂性
1)贪心选择性质
dijkstra算法所做的贪心选择是从V-S中选择具有最短特殊路径的顶点u,从而确定源到u的最短路径长度
2)最优子结构
不论算法中dist[u]是否变化,它总是关于当前顶点集S到v的特殊最短路径长度