/*
給定一個帶權有向圖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;
}