单源最短路径.cpp

算法分析中的贪心算法的实现

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

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

const int maxint = 65000;
template< class Type >
void Dijkstra( int n, int v, Type dist[], int prev[], Type **c )
{
	bool s[maxint];
	for( int i = 1; i <= n; ++i )
	{
		dist[i] = c[v][i];
		s[i] = false;
		if ( dist[i] == maxint )
		{
			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 j = 1; j <= n; ++j )
		{
			if ( (!s[j]) && (dist[j] < temp) )
			{
				u = j;
				temp = dist[j];
			}
		}
		s[u] = true;
		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;
				}
			}
		}
	}
}

/*
算法的正确性和计算复杂性：
（1）贪心选择性质
事实上如果存在一条从源到u且比dist[u]更短的路，设这条路初次走出S之外到达的顶点为
x属于V-S，然后徘徊于S内外若干次后，最后离开S到达u。
在这条路上，分别记d(v,x),d(x,u)和d(v,u)为顶点v到顶点x,顶点x到顶点n和顶点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]。此为矛盾，因为此时u就
不是最优的点了。这就
证明了dist[u]是从源点到顶点u的最短路径长度。
（2）最优子结构性质

*/
int main()
{
	return 0;
}