弗洛伊德算法

1、#include #include #include #include #include clock_t start,finish;long double duration;#define MAX_NAME 5#define MAX_INFO 20#define INFINITY INT_MAX/顶点字符串的最大长度+1/相关信息字符串的最大长度+1/用整型最大值代替8/最大顶点个数#define MAX_VERTEX_NUM 100typedef char VertexTypeMAX_NAME;/ 顶点数据类型及长度typedef enumDG, DN, AG AN GraphKind; /

2、 (有向图，有向网,无向图，无向网 /邻接矩阵的数据结构typedef structint adj; /顶点关系类型。对无权图，用1（是）或0（否）表示相邻否;/对带权图，则为权值类型ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 图的数据结构typedef structAdjMatrix arcs;/邻接矩阵int vexnum,/图的当前顶点数arcnum;/图的当前弧数GraphKind kind;/图的种类标志 MGraph;typedefintPathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUMMAX_VERT

3、EX_NUM;typedef int DistancMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/采用数组(邻接矩阵)表示法，构造有向网G。/int CreateDN(MGraph *G,FILE *F,FILE *IN)int CreateDN(MGraph *G,FILE *F)int i,j,k,w,t,m100;int n=0;printf(-请输入有向网G的顶点数:”n);scanf(%d%*c, &(*G).vexnum);fprintf(F,%ldt ,(*G).vexnum);/fprintf(F,”边数:ldt ”,(*G).arcnum);for(

4、i=0;i(*G).vexnum;+i) / 初始化邻接矩阵for(j=0;j(*G).vexnum;+j) if(i=j) (*G).arcsij.adj=0;else(*G).arcsij.adj=INFINITY; /网，边的权值初始化为无穷大/自动生成邻接矩阵for(i=0;iv(*G).vexnum;i+)printf(请输入第d个数需要产生的边的个数(小于d):n”,i,(*G).vexnum-2); scanf(%d”,&t);for(j=0; j t; +j)int x=0;mj=int(rand()%(*G).vexnum);while(xvj&mx!=mj) / 没找到循环

5、x=x+1;if(i!=mj)&x=j) 没有找到同样的数或i!=j(*G).arcsimj.adj=int(rand()%(100-1)+1;printf(*G).arcsimj.adj:%dn”,(*G).arcsimj.adj);else j=j-1;/*for(k=0;kv(*G).vexnum*(*G).vexnum);+k)i = k/(*G).vexnum;j = k%(*G).vexnum;fscanf(IN,”%d”,&w);if(w!=0&w!=-1) n=n+1;(*G).arcsij.adj=w; / 有向网，弧的权值为 wif(*G).arcsij.adj=-1)(*

6、G).arcsij.adj=INFINITY;(*G).arcnum=n;printf(n:%dn,n);printf(*G).arcnum:%dn,(*G).arcnum); */ printf(初始邻接矩阵:n);for(i=0;i(*G).vexnum;i+) for(j=0;j(*G).vexnum;j+)printf(%d ”,(*G).arcsij.adj); printf(n);(*G).kind=DN;有向网的种类标志return 1;long double ShortestPath_FLOYD(MGraph G,FILE *F)duration=0;start=clock()

7、;int i,j,k;for(k=0;kG.vexnum;k+) for(i=0;iGvexnum;i+)for(j=0;j0) if(Garcsik.adj)+(G.arcskj.adj)(G.arcsij.adj) Garcsij.adj = G.arcsik.adj+Garcskj.adj; /*printf(第d 次邻接矩阵:n,k);for(i=0;iGvexnum;i+) for(j=0;jGvexnum;j+)printf(%d ,G.arcsij.adj);printf(n); */finish=clock();duration=(double)(finish - start)

8、/CLOCKS_PER_SEC;printf(zuizhong 矩阵:n);for(i=0;iGvexnum;i+)for(j=0;jGvexnum;j+)printf(%6d ,Garcsij.adj);printf(n);for(i=0;iGvexnum;i+)for(j=0;jGvexnum;j+)printf(%d 到d 的最短距离%dn,i,j,Garcsij.adj);return duration;int main()MGraph g;int i,j;FILE *f,*out;char file10,file210;/*printf(输入要读入的文件名：n);scanf(%s,file2);if(out=fopen(file2,r)=NULL)printf(can not open the read file2!n);exit(0); */printf(输入要生成的文件名：n);scanf(%s,file);if(f=fopen(file,w)=NULL)printf(can not open the file!n);exit(0);CreateDN(&g,f);printf(初始邻接矩阵:n)