《图的最短路径算法的实现》由会员分享，可在线阅读，更多相关《图的最短路径算法的实现（7页珍藏版）》请在金锄头文库上搜索。
1、图的最短路径算法的实现C语百#include#include#include#defineINF32767#defineMAXV100#defineBUFLEN1024typedefstructcharname100;charinfo1000;VertexType;typedefstructVertexTypevexs10;intarcs100100;intvexnum,arcnum;MGraph;图结构char*getFile(charfileName口,char*array口,int&count)FILE*file;charbufBUFLEN;intlen=0;文件读取的长度file=fo
2、pen(fileName,rt);打开graph.txt的信息if(file=NULL)文件为空的处理办法printf(Cannotopenfilestrikeanykeyexit!n);exit(1);while(fgets(buf,BUFLEN,file)len=strlen(buf);arraycount=(char*)malloc(len+1);if(!arraycount)break;strcpy(arraycount+,buf);fclose(file);returnarray;voidgetInfo(int&vex,int&arc,char*array)charbuf_ch100
3、;char*ch100;char*tokenp;intstr_count=0,str_len=0;tokenp=strtok(array,);strcpy(buf_ch,tokenp);while(tokenp!=NULL)str_len=strlen(tokenp);chstr_count=(char*)malloc(str_len+1);strcpy(chstr_count+,tokenp);tokenp=strtok(NULL,);for(inti=0;istr_count;i+)if(i%2=1)chistrlen(chi)-1=0;sscanf(chi,%d,&arc);elsess
4、canf(chi,%d,&vex);MGraphsetVertexTypeInfo(MGraphg,char*arrayVer)intstr_count=0;charbuf_ch100;char*ch100;char*tokenp;for(inti=0;ig.vexnum+1&arrayVerg.vexnum;i+)intstr_len=0;tokenp=strtok(arrayVeri,);strcpy(buf_ch,tokenp);while(tokenp!=NULL)str_len=strlen(tokenp);chstr_count=(char*)malloc(str_len+1);s
5、trcpy(chstr_count+,tokenp);tokenp=strtok(NULL,);for(inti1=2;i1str_count;i1+)if(i1%2=1)chi1strlen(chi1)-1=0;strcpy(g.vexsi1/2-1.info,chi1);elsestrcpy(g.vexsi1/2-1.name,chi1);returng;设置无向图的基本信息MGraphsetMGraphInfo(MGraphg,char*arrayMGraph,int&count)intstr_count=0;charbuf_ch100;char*ch100;char*tokenp;fo
6、r(inti4=g.vexnum+1;i4count;i4+)intstr_len=0;tokenp=strtok(arrayMGraphi4,);strcpy(buf_ch,tokenp);while(tokenp!=NULL)str_len=strlen(tokenp);chstr_count=(char*)malloc(str_len+1);strcpy(chstr_count+,tokenp);tokenp=strtok(NULL,);char*info8;需要匹配的字符串集合for(inti2=0;i2g.vexnum;i2+)infoi2=g.vexsi2.name;intG505
7、0;邻接矩阵初始化for(inti3=0;i3g.vexnum;i3+)for(intj=0;jg.vexnum;j+)Gi3j=INF;inttemp100=0;存储距离信息inttemp_count=0;距离计数器inttempleft100=0;起始地址的代号信息inttempleft_count=0;起始地址计数器inttempright100=0;/终点地址的代号信息inttempright_count=0;终点地址的计数器for(intk=0;kstr_count;k+)if(k%3=0)for(intm=0;mg.vexnum;m+)if(strcmp(infom,chk)=0)
8、templefttempleft_count+=m;elseif(k%3=1)for(intm=0;mg.vexnum;m+)if(strcmp(infom,chk)=0)temprighttempright_count+=m;elseif(k%3=2)chkstrlen(chk)-1=0;sscanf(chk,%d,&temptemp_count+);for(inti5=0;i5temp_count;i5+)Gtemplefti5temprighti5=tempi5;for(inti6=0;i6g.vexnum;i6+)建立图的邻接矩阵for(intj=0;jg.vexnum;j+)g.ar
9、csi6j=Gi6j;)returng;)voidDispMat(MGraphg)(inti,j;for(i=0;ig.vexnum;i+)(for(j=0;j,g.vexsk.name);ppath(g,path,k,j);)voidDisPath(MGraphg,intA口MAXV,intpath口MAXV,inti,intj)(if(Aij=INF)(if(i!=j)printf(从%s至U%s没有路径n,g.vexsi.name,g.vexsj.name);)elseprintf(%s-,g.vexsi.name);ppath(g,path,i,j);printf(%s,g.vexsj
10、.name);printf(t路径长度为:%dn,Aij);)voidFloyd(MGraphg,intp,intq)弗洛伊德算法intAMAXVMAXV,pathMAXVMAXV;inti,j,k,n=g.vexnum;for(i=0;in;i+)for(j=0;jn;j+)Aij=g.arcsij;pathij=-1;for(k=0;kn;k+)(for(i=0;in;i+)for(j=0;j(Aik+Akj)Aij=Aik+Akj;pathij=k;)printf(最短路径为：n);DisPath(g,A,path,p,q);输出最短路径)intmain()intvex,arc;prin
11、tf(欢迎来到江西理工大学n);printf(n);MGraphg;图的定义char*array1;存储顶点和边数数据信息char*arrayVer10;/存储地点信息char*arrayMGraphMAXV;存储关于图的信息intcount=0;数据Z构shujujiegouyNgraph.txt;getFile(fileName,array,count);/printf(%dn,count);count=0;getInfo(vex,arc,array0);g.vexnum=vex;g.arcnum=arc;getFile(fileName,arrayVer,count);count=0;g
12、=setVertexTypeInfo(g,arrayVer);getFile(fileName,arrayMGraph,count);g=setMGraphInfo(g,arrayMGraph,count);DispMat(g);printf(江西理工大学校园导向图nn);printf(功能选项：nn);printf(1.查看所有景点nn);printf(2.查询景点信息nn);printf(3.查询两个景点的最短路径nn);nn);printf(4.退出校园导游nn);printf(返回到所有景点请输入9(功能3辅助)intn=0,m=0,p=0,q=0,flag=0;inti7=0;while(n!=4)flag=scanf(%d,&n);while(flag!=1)fflush(stdin);printf(对不起，您输入的有误，请重输入n);flag=scanf(%d,&n);)switch(n)loopl:case1:printf(校园的景点有：n);for(i7=0;i7g.vexnum;i7+)printf(%d.%sn,i7+1,g.vexsi7.name);)printf(需要继续查询请选择功能选项，否则按4退出n
