#include <iostream>
using namespace std;

#define MAXV 50
#define INF 10000

typedef int InfoType;

//鄰接矩陣存儲方法
/*typedef struct
{
    int no;
    InfoType info;
} VertexType;
*/
typedef struct
{
	int edges[MAXV][MAXV];
    int n;
    //VertexType vexs[MAXV];
} MGraph;

//狄克斯特拉算法
void Ppath(int path[],int i,int v)//遞歸輸出經過的中間節點
{
    int k;
    k=path[i];
    if(k==v) return;
    Ppath(path,k,v);
    cout<<k;
}


void Dispath(int dist[],int path[],int s[],int n,int v)
{
    int i;
    for(i=0;i<n;i++)
	{
        if(i==v) continue;
        if(s[i]==1)
		{
			cout<<"從DS"<<"到S"<<i<<"的最短路徑為："<<dist[i]<<" ";
            cout<<v;        //輸出起點
            Ppath(path,i,v);//輸出經過的中間節點
            cout<<i<<endl;  //輸出終點
		}
		else
			cout<<"從DS"<<"到S"<<i<<"不存在的路徑"<<endl;
	}
}

//狄克斯特拉算法
void Dijkstra(MGraph g,int v)
{   //dist[]存儲節點s[]的最短路徑；
	//path[]存儲路徑終點的上一個節點；
	int dist[MAXV],path[MAXV];
	int s[MAXV];
    int mindis,i,j,u;
    for(i=0;i<g.n;i++)
	{
		dist[i]=g.edges[v][i];
        s[i]=0;
        if(g.edges[v][i]<INF) path[i]=v;
		else path[i]=-1;
	}
	s[v]=1;path[v]=0;
	for(i=0;i<g.n;i++)
	{
		mindis=INF;
		for(j=0;j<g.n;j++)//判斷可以通過那些其他中間節點s[u]進行松弛
		{
			if(s[j]==0&&dist[j]<mindis)
			{
				u=j;
				mindis=dist[j];
			}
		}
		s[u]=1;//DS通過節點s[u]進行松弛
		for(j=0;j<g.n;j++)
		{
			if(s[j]==0)
			{
				if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])
				{
					dist[j]=dist[u]+g.edges[u][j];
					path[j]=u; //把經過的中間節點存入path[]
				}
			}
		}
	}
	Dispath(dist,path,s,g.n,v);
}

//弗洛伊德算法
void Ppath1(int path[][MAXV],int i,int j)
{
	int k;
	k=path[i][j];
	if(k==-1) return;
	cout<<k;
	Ppath1(path,k,j);
}

void Dispath1(int A[][MAXV],int path[][MAXV],int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i==j) continue;
			if(A[i][j]==INF)//無窮大
			{
				if(i!=j)
					cout<<"從"<<i<<"到"<<j<<"不存在路徑"<<endl;
			}
			else
			{
				cout<<"從"<<i<<"到"<<j<<"的最短路徑長度為:"<<A[i][j]<<" ";
				cout<<i;
				Ppath1(path,i,j);
				cout<<j<<endl;
			}
		}
	}
	//輸出變換后的矩陣
	cout<<"變換后的A[i][j]矩陣為："<<endl;
	for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				cout<<A[i][j];
			}
		}
	cout<<endl;
	for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				cout<<path[i][j];
			}
		}
}

//弗洛伊德算法
void Floyd(MGraph g)
{
	int A[MAXV][MAXV],path[MAXV][MAXV];
	int i,j,k;
	for(i=0;i<g.n;i++)
	{
		for(j=0;j<g.n;j++)
		{
			A[i][j]=g.edges[i][j];
			path[i][j]=-1;
		}
	}
	for(k=0;k<g.n;k++)//K為經過的中間節點
	{
		for(i=0;i<g.n;i++)//i為源點
		{
			for(j=0;j<g.n;j++)//j為終點
			{
				if(A[i][j]>A[i][k]+A[k][j])
				{
					A[i][j]=A[i][k]+A[k][j];
					path[i][j]=k;
				}
			}
		}
	}
	Dispath1(A,path,g.n);
}

//主函數
int main()
{
	int i,j,n;
	MGraph g;
	cout<<"請輸入帶權圖的頂點個數：";//例如輸入4
	while(scanf("%d",&n)!=EOF/*cin>>n,n!=EOF*/)
	{
		cout<<"請輸入帶權圖的鄰接矩陣："<<endl;
/*輸入格式如下
0 1 3 7
6 0 4 3
1 4 0 2
5 7 1 0
*/

		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
                //scanf("%d",&g.edges[i][j]);
				cin>>g.edges[i][j];
			}
		}
		g.n=n;
		cout<<"采用迪杰斯特拉算法得到的最短路徑為："<<endl;
        
		Dijkstra(g,0);
        
		Dijkstra(g,3);
		
		cout<<endl;

		cout<<"采用弗洛伊德算法得到的最短路徑為："<<endl;
		Floyd(g);
		
		cout<<endl;
		break;
	}
	return 0;
}