#include<iostream.h>
#include<iomanip.h>
#define INFINITY 10000//INT_MAX
#define MAX_VERTEX_NUM 20
typedef struct ArcCell{
int adj;
int *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct Distance{
int distance;
}DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
char data;
}VertexType;
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];//定义顶点类型
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
int locatevex(MGraph G,char v)
{
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i].data==v)
return i;
return -1;
}
void Creatgraph(MGraph &G)
{ int i,j,k,weight;
char v1,v2;
cout<<"请输入图的顶点数和弧数"<<endl;
cin>>G.vexnum >>G.arcnum;
for(i=0;i<G.vexnum;i++)
{ cout<<"输出第"<<i<<"个顶点:";
cin>>G.vexs[i].data;
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
if(j==i)G.arcs[i][j].adj=0;
else G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;
}
for(k=0;k<G.arcnum;k++)
{
cout<<"请输入有弧相连的顶点A与顶点B的信息以及它们之间的弧的权值："<<endl;
cin>>v1>>v2>>weight;
i=locatevex(G,v1);
j=locatevex(G,v2);
G.arcs[i][j].adj=weight;
//G.arcs[j][i].adj=G.arcs[i][j].adj;
}
cout<<endl;
cout<<"所构造的矩阵输出如下："<<endl;
cout<<setw(20)<<G.vexs[0].data;
for(i=1;i<G.vexnum;i++)
cout<<setw(10)<<G.vexs[i].data;
cout<<endl;
for( i=0;i<G.vexnum;i++)
{ cout<<setw(10)<<G.vexs[i].data;
for(j=0;j<G.vexnum;j++)
cout<<setw(10)<<G.arcs[i][j].adj;
cout<<endl;
}
cout<<endl;
}
void ShortestPath_FLOYD(MGraph G,DistancMatrix &D)
{
int u,v,w;
char P[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
for( v=0;v<G.vexnum;++v)
for( w=0;w<G.vexnum;++w)
{
D[v][w].distance=G.arcs[v][w].adj;
if(D[v][w].distance<INFINITY )
P[v][w]=G.vexs[v].data;
else P[v][w]=-1;
}
int k=0;
for( u=0;u<G.vexnum;++u)
{
//cout<<"P("<<k<<")"<<"************"<<"D("<<k<<")"<<"************"<<endl;
k++;
for(v=0;v<G.vexnum;++v)
{
for(w=0;w<G.vexnum;++w)
{
//cout<<"顶点"<<G.vexs[v].data;
//cout<<"到顶点"<<G.vexs[w].data<<"的最短路径为:"<<endl;
//cout<<G.vexs[v].data<<'\t';
if((D[v][u].distance+D[u][w].distance)<D[v][w].distance)
{
D[v][w].distance=D[v][u].distance+D[u][w].distance;
P[v][w]=G.vexs[u].data;
//cout<<P[v][w]<<'\t';
}
// cout<<G.vexs[w].data;
// cout<<endl;
//cout<<"-----------------------"<<endl;
//cout<<"-----------------------------------------------------------------------"<<endl;
// cout<<"-----------------------------------------------------------------------"<<endl;
// cout<<"顶点"<<G.vexs[v].data<<"与顶点"<<G.vexs[w].data<<"的最短路径长度为";
// cout<<D[v][w].distance<<endl;
}
}//cout<<endl;
}
for(v=0;v<G.vexnum;++v)
for(w=0;w<G.vexnum;++w)
{ cout<<"顶点"<<G.vexs[v].data<<"与顶点"<<G.vexs[w].data<<"的最短路径长度为";
cout<<D[v][w].distance<<endl;
cout<<"*********************************"<<endl;
cout<<"顶点"<<G.vexs[v].data;
cout<<"到顶点"<<G.vexs[w].data<<"的最短路径为:"<<endl;
cout<<G.vexs[v].data<<'\t';
if(P[v][w]!=G.vexs[v].data)
{cout<<P[v][w]<<'\t';}
cout<<G.vexs[w].data<<endl;
cout<<"--------------------------------------"<<endl;
cout<<"--------------------------------------"<<endl;
}
cout<<"******************************最短路径求解完成******************************"<<endl;
}
void main()
{
MGraph G;
DistancMatrix D;
cout<<"***********************************图的应用***********************************"<<endl;
Creatgraph(G);
ShortestPath_FLOYD(G,D);
}
