弗洛伊德算法

弗洛伊德算法 #include "stdio.h" #include "iostream.h" #include "stdlib.h" #include <iostream> #define INFINITY 32767//int型的最大值为∞ #define MAX_VEX_NUM 30//最大顶点个数 typedef struct{ char vexs[MAX_VEX_NUM+1];//顶点信息 int arcs[MAX_VEX_NUM+1][MAX_VEX_NUM+1];//邻接矩阵存放权值 int vexnum,arcnum;//顶点数,弧(边)数 }AdjGraph; int CenterVex(AdjGraph *g);//带权图的邻接矩阵建立 AdjGraph *CreateAdjGrahp();//Floyd算法 void main() { int k; AdjGraph *g; g=CreateAdjGrahp(); k=CenterVex(g); cout<<"中心顶点为:"<<g->vexs[k]<<endl; } ////////////////邻接矩阵的建立//////////////// AdjGraph *CreateAdjGrahp() { AdjGraph *g; g=new AdjGraph; int i,j,k,x; cout<<"Input vexnum and arcnum(格式如:顶点数 边数<Enter>):"<<endl; scanf("%d%d",&g->vexnum,&g->arcnum);//读入顶点个数和边数 cout<<"输入顶点信息:(如:abcde<Enter>)"<<endl; scanf("%c",&g->vexs[1]); for(i=1;i<=g->vexnum;i++) scanf("%c",&g->vexs[i]);//读入顶点信息 for(i=1;i<=g->vexnum;i++) for(j=1;j<=g->vexnum;j++) g->arcs[i][j]=INFINITY;//初始化邻接矩阵 cout<<"顶点<->序号"<<endl; for(k=1;k<=g->vexnum;k++) { printf("L<->%d",g->vexs[k],k); cout<<endl; } cout<<"输入每条边对应的两个顶点的序号及权值,格式为:"<<endl <<"i j x<Enter>"<<endl; for(k=1;k<=g->arcnum;k++) { scanf("%d%d%d",&i,&j,&x);//输入边信息，建立邻接矩阵 g->arcs[i][j]=x; } return g; }//CreateGraph