图的最短路径算法的实现

图的最短路径算法的实现

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]; //存储关于图的信息