#include <stdio.h>
#include <iostream.h>
#include <ctype.h>
int C[5][5],D[5],T[5],F[5];
int *current_T,temp,i,w,v,n,k,j,line,file,a=0;
FILE *fp;
/*
根據大連理工的《數據結構》課本自己寫的Dijkstra算法		
我設置的是0，1，2，3，4這5個頂點
從文件讀取頂點之間的路徑數據
每一次篩選過后都會把最短路的輸出結果顯示一次
當時的目的是和書上的對比，因為測試的數據就是再書中找的題	
它列出了每次篩選后的數據，這樣方便我調試。
最后的結果和書上的一模一樣
*/


void main()
{
	if((fp=fopen("1.txt","r+"))!=NULL)
	{
		while(!feof(fp))
		{
			if(a==0)
			{
				fscanf(fp,"%d",&n);
				printf("%d\t",n);
				a=1;
				for(i=0;i<n;i++)
				{
					T[i]=20000;
					F[i]=20000;
				}
			}
			else
			{
				for(line=0;line<n;line++)
					for(file=0;file<n;file++)
					{
						fscanf(fp,"%d",&C[line][file]);
					}	
			}
		}
	}
	if(fp!=NULL)
		fclose(fp);

	current_T=T;
	T[0]=0;
	F[0]=1;
	F[1]=2;
	F[2]=3;
	F[3]=4;
	isalnum(T[0]);
	for(i=1;i<n;i++)
	{
		D[i]=C[0][i];
	}
	for(int r=0;r<n-1;r++)
	{
		temp=20000; 
	
		for(i=0;T[i]!=20000;i++)
		{
			for(j=0;F[j]!=20000;j++)
			{
				if(temp>C[T[i]][F[j]])
				{
					temp=C[T[i]][F[j]]; 
					w=F[j]; 
				}
			}
		}
		cout<<endl<<"w:"<<w<<endl;
		for(int e=1;e<n;e++)
		{
			cout<<"D["<<e<<"]:"<<D[e]<<" ";
		}
		current_T++;
		(*current_T)=w;
		while(F[k]!=20000) 
		{ 
			F[k]=F[k+1];
			k++;
		}

		for(j=0;F[j]!=20000;j++)
		{
			v=F[j];
			D[v]=D[v]<(D[w]+C[w][v])?D[v]:(D[w]+C[w][v]);
		}
		cout<<endl<<"－－－－－－－－－－－－－－－－－－－－－－"<<endl;
	}
	for(j=1;j<n;j++)
	{
		cout<<"源點0到點"<<j<<"的最短距離為:";
		cout<<"D["<<j<<"]="<<D[j]<<endl;
	}
	getchar();


}