#include<iostream.h>
#include<malloc.h>
#include<iomanip.h>

const int maxint=1000;

void dijstra(int n,int v,int*dist,int prev[],int **c)
{
	//單源點最短路徑問題的dijstra算法

	int s[maxint];
	for(int i=0;i<n;i++)
	{
		dist[i]=c[v][i];
		s[i]=0;//標記是否為S集合中的點
	    if(dist[i]==maxint) prev[i]=0;
		else
			prev[i]=v;
	}

	dist[v]=0;s[v]=1;

	cout<<"初始:"<<endl;
	for(i=0;i<n;i++)
		cout<<setw(5)<<dist[i]<<"  ";
	cout<<endl;
	cout<<endl<<endl;


	for(i=0;i<n;i++)
	{
		cout<<"當前迭代次數"<<i+1<<endl;


		int temp=maxint;
		int u=v;

		for(int j=0;j<n;j++)
			if((!s[j])&&(dist[j]<temp))
			{
				u=j;temp=dist[j];
			}//endif endfor

		s[u]=1;//選取具有最小費用的點放入S中
		
		cout<<u+1<<"結點被放入S集合中"<<endl;


		//用u更新每個結點的dist
		for(j=0;j<n;j++)
		{
			if((!s[j])&&(c[u][j]<maxint))
			{
				int newdist=dist[u]+c[u][j];
				if(newdist<dist[j])
				{
					cout<<"結點"<<j+1<<"由"<<dist[j]<<"更新為"<<newdist<<endl;
					dist[j]=newdist;
					prev[j]=u;
				}//endif
			}//endif

		}//endfor


				
	for(j=0;j<n;j++)
		cout<<setw(5)<<dist[j]<<"  ";
	cout<<endl;
	cout<<endl<<endl;
	}//endfor




}//endldijstra


void main()
{
	int i,j;
	int **c,*dist,*prev;

	int n=5;

	c=(int **)malloc(sizeof(int *)*n);
	for(i=0;i<n;i++)
	{
		c[i]=(int*)malloc(sizeof(int)*n);
	}
	

	dist=(int*)malloc(sizeof(int)*n);
	prev=(int*)malloc(sizeof(int)*n);


	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			c[i][j]=maxint;
		}
		

	c[0][1]=10;
	c[0][3]=30;
	c[0][4]=100;
	c[1][2]=50;
	c[2][4]=10;
	c[3][2]=20;
	c[3][4]=60;


	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
		
			cout<<setw(5)<<c[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;


	dijstra(n,0,dist,prev,c);


	cout<<"result:"<<endl;
	for(i=0;i<n;i++)
		cout<<setw(5)<<dist[i]<<"  ";
	cout<<endl;
	

	delete[] prev;
	delete[] dist;

	for(i=0;i<n;i++)
		delete[] c[i];
	delete[] c;

}