zuiduanlujing.cpp

以邻接矩阵为存储结构

#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);
	
}