zuiduanlujing.rar_zuiduanlujing

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