图的最短路径算法的实现

图的最短路径算法的实现

C语言

#include #include #include #define INF 32767 #define MAXV 100 #define BUFLEN 1024 typedef struct

{ char name[100]; char info[1000]; } VertexType; typedef struct { VertexType vexs[10]; int arcs[100][100]; int vexnum,arcnum; } MGraph; //图结构

char** getFile(char fileName[],char *array[],int &count){ FILE *file; char buf[BUFLEN]; int len=0; //文件读取的长度 file=fopen(fileName,\//打开graph.txt的信息 if(file==NULL) //文件为空的处理办法 { printf(\ exit(1); } while(fgets(buf,BUFLEN,file)) { len=strlen(buf); array[count]=(char*)malloc(len+1); if(!array[count]) break; strcpy(array[count++],buf); } fclose(file); return array; }

void getInfo(int &vex,int &arc,char *array){ char buf_ch[100];

char *ch[100]; char *tokenp; int str_count=0,str_len=0; tokenp=strtok(array,\ strcpy(buf_ch,tokenp); while(tokenp!=NULL) { str_len=strlen(tokenp);

ch[str_count]=(char*)malloc(str_len+1); strcpy(ch[str_count++],tokenp); tokenp=strtok(NULL,\ } for(int i=0;i

MGraph setVertexTypeInfo(MGraph g,char *arrayVer[]){ int str_count=0; char buf_ch[100]; char *ch[100]; char *tokenp; for(int i=0;i

} } return g; }

//设置无向图的基本信息

MGraph setMGraphInfo(MGraph g,char *arrayMGraph[],int &count){ int str_count=0; char buf_ch[100]; char *ch[100]; char *tokenp; for(int i4=g.vexnum+1;i4

for(int m=0;m

void DispMat(MGraph g) { int i,j; for(i=0;i

void ppath(MGraph g,int path[][MAXV],int i,int j) { int k; k=path[i][j]; if (k==-1) return; ppath(g,path,i,k); printf(\ ppath(g,path,k,j); }

void DisPath(MGraph g,int A[][MAXV],int path[][MAXV],int i,int j) { if (A[i][j]==INF)

{ if (i!=j) printf(\从 %s 到 %s 没有路径\\n\ } else{ printf(\ printf(\路径长度为:%d\\n\ } }

void Floyd(MGraph g,int p,int q) //弗洛伊德算法 { int A[MAXV][MAXV],path[MAXV][MAXV]; int i,j,k,n=g.vexnum; for (i=0;i(A[i][k]+A[k][j])) { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } } printf(\最短路径为:\\n\ DisPath(g,A,path,p,q); //输出最短路径 }

int main() { int vex,arc; printf(\ 欢迎来到江西理工大学 \\n\ printf(\ \\n\ MGraph g; //图的定义 char *array[1]; //存储顶点和边数数据信息 char *arrayVer[10]; //存储地点信息 char *arrayMGraph[MAXV]; //存储关于图的信息

int count=0; char fileName[]=\数据结构\\\\shujujiegouyi\\\\graph.txt\ getFile(fileName,array,count); //printf(\ count=0; getInfo(vex,arc,array[0]); g.vexnum=vex; g.arcnum=arc; getFile(fileName,arrayVer,count); count=0; g=setVertexTypeInfo(g,arrayVer); getFile(fileName,arrayMGraph,count); g=setMGraphInfo(g,arrayMGraph,count); DispMat(g); printf(\江西理工大学校园导向图 \\n\\n\ printf(\功能选项： \\n\\n\ printf(\ 1.查看所有景点 \\n\\n\ printf(\ 2.查询景点信息 \\n\\n\ printf(\ 3.查询两个景点的最短路径 \\n\\n\ printf(\ 4.退出校园导游 \\n\\n\ printf(\返回到所有景点请输入9（功能3辅助） \\n\\n\ int n=0,m=0,p=0,q=0,flag=0;int i7=0; while(n!=4){ flag=scanf(\ while(flag!=1) { fflush(stdin);

printf(\对不起，您输入的有误，请重输入\\n\ flag=scanf(\ } switch(n){ loop1: case 1: printf(\校园的景点有：\\n\ for(i7=0;i7

} if(m<9&&m>0){ printf(\的信息:%s\\n\ printf(\需要继续查询请选择功能选项，否则按4退出\\n\ } else{ printf(\您输入的数字有误，请输入(1-8)\\n\ goto loop2; } break; case 3: printf(\请输入您要查询第一个的景点:(1-8)\\n\

loop3: flag=scanf(\ while(flag!=1) { fflush(stdin);

printf(\对不起，您输入的不是数字，请输入数字\\n\ flag=scanf(\ } if(p==9){ goto loop1; } if(p<9&&p>0){ printf(\请输入您要查询第二个的景点:(1-8)\\n\ } else{ printf(\您输入有误，请重新输入要查询的第一个景点(1-8)\\n\ goto loop3; }

loop4: flag=scanf(\ while(flag!=1) { fflush(stdin);

printf(\对不起，您输入的数字有误，请输入数字(1-8)\\n\ flag=scanf(\ } if(q==9) goto loop1; if(q<9&&q>0){ Floyd(g,p-1,q-1); printf(\需要继续查询请选择功能选项，否则按4退出\\n\ } else{ printf(\您输入有误，请重新输入要查询的第二个景点(1-8)\\n\

}

} } return 0;

goto loop4; } break;

case 4: printf(\欢迎再来\\n\

default : printf(\输入错误，请输入1-3的数字！\\n\

本文来源：https://www.bwwdw.com/article/06pp.html