#include<iostream>
#include<string>
using namespace std;
#define maxnum 100
#define maxlength 10000
typedef int ElemType;
typedef int WType;
typedef struct{
ElemType tu[maxnum][maxnum]; //邻接矩阵
string point[maxnum]; //顶点矩阵
int point_num; //顶点个数
}Graph;
void input(Graph &G)
{
cout<<"请输入图的顶点数:";
cin>>G.point_num;
cout<<"请输入顶点的信息:"<<endl;
for(int j=0;j<G.point_num;j++)
cin>>G.point[j];
cout<<"请输入图的邻接矩阵:"<<endl;
for(int i=0;i<G.point_num;i++)
{
for(int j=0;j<G.point_num;j++)
cin>>G.tu[i][j];
}
}
void Floyd(Graph &G,WType a[][maxnum],int path[][maxnum])
//a[i][j]是顶点i和j之间的最短路径长度，path[i][j]是相应路径上顶点j的前一顶点的顶点号
{
int i,j,k;
for(i=0;i<G.point_num;i++) //矩阵a与path的初始化
for(j=0;j<G.point_num;j++)
{
a[i][j]=G.tu[i][j];
if((i!=j)&&(a[i][j]<maxlength))
path[i][j]=i;
else
path[i][j]=i;
}
for(k=0;k<G.point_num;k++)//针对每一个k，产生a(K),path(k)
for(i=0;i<G.point_num;i++)
for(j=0;j<G.point_num;j++)
if((a[i][k]+a[k][j])<a[i][j])
{
a[i][j]=a[i][k]+a[k][j];
path[i][j]=path[k][j];//缩短路径长度，绕过k到j
}
}
void printShortPath(Graph&G,WType dist[][maxnum],int path[][maxnum])
//a[i][j]是顶点i和j之间的最短路径长度，path[i][j]是相应路径上顶点j的前一顶点的顶点号
{
//system("pause");
cout<<"各对顶点的最短路径为:"<<endl;
int i,j,k,l;
int d[maxnum];
for(i=0;i<G.point_num;i++)
{
for(l=0;l<G.point_num;l++)
{
if(l!=i)
{
j=l; k=0;
if(dist[i][l]==maxlength)
{
cout<<"源点"<<G.point[i]<<"到"<<G.point[l]<<"之间无路径"<<endl;
}
else
{
while(j!=i) //起点没有在d【k】数组里
{
d[k++]=j; //第一次j是中点
j=path[i][j];
}
cout<<"顶点"<<G.point[i]<<"到顶点"<<G.point[l]<<"的最短路径为:"<<G.point[i]<<" ";
while(k>0)
{
cout<<G.point[d[--k]]<<" ";
}
cout<<"\t\t最短路径的长度为:"<<dist[i][l]<<endl;
}
}
}
}
}
int main()
{
Graph G;
WType dist[maxnum][maxnum];
int path[maxnum][maxnum];
input(G);
Floyd(G,dist,path);
printShortPath(G,dist,path);
// system("pause");
return 0;
}
/*
4
V0 V1 V2 V3
0 1 10000 4
10000 0 9 2
3 5 0 8
10000 10000 6 0
0
*/
/*
6
V0 V1 V2 V3 V4 V5
10000 10000 10 10000 30 100
10000 10000 5 10000 10000 10000
10000 10000 10000 50 10000 10000
10000 10000 10000 10000 10000 10
10000 10000 10000 20 10000 60
10000 10000 10000 10000 10000 10000
0
*/