#include <iostream>
using namespace std ;
const N = 10 ;
const  MaxWeight = 9999 ;
int a[N][N] ;
int n ; // 頂點(diǎn)的個數(shù)

void Dijkstra( int v0, int distance[], int path[])
//網(wǎng)G從頂點(diǎn)v0到其它頂點(diǎn)的最短距離distance和最短路徑path
{
	int *s = new int[n];
	int minDis, i, j, u;

	//初始化 
	for(i = 0; i < n; i ++)								
	{
		distance[i] = a[v0][i] ;
		s[i] = 0;
		if(i != v0 && distance[i] < MaxWeight) path[i] = v0;
		else path[i] = -1;
	}
	s[v0] = 1;       //標(biāo)記頂點(diǎn)v0已從集合T加入到集合S中 

	//在當(dāng)前還未找到最短路徑的頂點(diǎn)集中選取具有最短距離的頂點(diǎn)u 
	for(i = 1; i < n; i ++)
	{
		minDis = MaxWeight;
		for(j = 0; j < n; j ++)
			if(s[j] == 0 && distance[j] < minDis)
			{
				u = j;
				minDis = distance[j];
			}

		if(minDis == MaxWeight) return;		//當(dāng)已不再存在路徑時算法結(jié)束

		s[u] = 1;     //標(biāo)記頂點(diǎn)u已從集合T加入到集合S中

		//修改從v0到其它頂點(diǎn)的最短距離和最短路徑
		for(j = 0; j < n; j++)
			if(s[j] == 0 && a[u][j] < MaxWeight && 
				distance[u] + a[u][j] < distance[j])
			{
				//頂點(diǎn)v0經(jīng)頂點(diǎn)u到其它頂點(diǎn)的最短距離和最短路徑
				distance[j] = distance[u] + a[u][j];
				path[j] = u;
			}
	}
}