中国石油大学数据结构上机实验8

1《数据结构》实验报告学号2015011512姓名胡明禹专业数学与应用数学时间2018.6.5一、实验题目:实验八最短路径二、实验目的1.掌握杰斯特拉算法2.利用迪杰斯特拉算法计算途中一点到其他各顶点的最短路径三、算法设计分析实验由4个函数共同组成。其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能voidmain()（2）创建有向图的邻接矩阵函数StatusCreateDG(MGraph&G){inti,j,k,w;charv1,v2;printf(请输入顶点数和边数：);scanf(%d%d,&G.vexnum,&G.arcnum);printf(\n请按次序输入%d个顶点字母标号(如ABCD等)：,G.vexnum);getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for(i=0;iG.vexnum;i++)scanf(%c,&G.vexs[i]);getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for(i=0;iG.vexnum;++i)//初始化邻接矩阵for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}printf(\n输入边的顶点和权值(如AB1):\n);//构造邻接矩阵for(k=0;kG.arcnum;k++){scanf(%c%c%d,&v1,&v2,&w);//输入一条有向边的起点终点和权值i=LocateVex(G,v1);//确定顶点在G中的位置j=LocateVex(G,v2);G.arcs[i][j].adj=w;2getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键}returnOK;}（3）输出邻接矩阵函数StatusPrintArcs(MGraph&G){inti;intj;printf(邻接矩阵\n);//按行序依次输出for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++){if(INFINITY==G.arcs[i][j].adj)printf(%6s%,INF);elseprintf(%6d,G.arcs[i][j]);}printf(\n);}returnOK;}（4）最短路径函数StatusShortestPath_DIJ(MGraphG,intv0,intp[],intD[]){//求有向网G的V0到其余顶点的最短路径P[v]及其带权长度D[v]//若p[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点//final[v]为TRUE当且仅当v∈S，即已经求得从v0到v的最短路径intm,v,i,w,j,k;intmin;intfinal[MAX_VERTEX_NUM];chara[MAX_VERTEX_NUM];for(v=0;vG.vexnum;++v){final[v]=FALSE;p[v]=FALSE;D[v]=G.arcs[v0][v].adj;}//forD[v0]=0;final[v0]=TRUE;//初始化，v0属于S//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集for(i=1;iG.vexnum;++i){min=INFINITY;3for(w=0;wG.vexnum;++w)if(!final[w])//w顶点在V-S中if(D[w]min){k=w;min=D[w];}//w离v0更近final[k]=TRUE;for(w=0;wG.vexnum;++w)//更新当前最短路径及距离if(!final[w]&&(min+G.arcs[k][w].adjD[w])){D[w]=min+G.arcs[k][w].adj;p[w]=k;}//if}//forprintf(dijkstra(%c):\n,G.vexs[v0]);for(i=0;iG.vexnum;i++){printf(最短路径长度(%c,%c)=%d\n,G.vexs[v0],G.vexs[i],D[i]);printf(最短路径为：);m=i;j=0;while(m!=v0){a[j]=G.vexs[m];m=p[m];j++;}a[j]=G.vexs[v0];for(m=j;m=0;m--){printf(%c,a[m]);}printf(\n);}returnOK;}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）4四、实验程序代码(该部分请加注释)#includestdio.h#includestdlib.h#includemalloc.h#includelimits.h#defineOK1#defineTRUE1#defineFALSE0#defineINFINITY65535//最大值无穷#defineMAX_VERTEX_NUM40//最大顶点个数typedefintInfoType;typedefintVRType;typedefcharVertexType;typedefintStatus;typedefstructArcCell{VRTypeadj;5InfoType*info;//该边相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的顶点数和有向边数}MGraph;intLocateVex(MGraph&G,VertexTypech){//返回顶点在G中顶点向量中的下标值inti;for(i=0;G.vexnum;i++)if(ch==G.vexs[i])returni;return-1;}StatusCreateDG(MGraph&G){//创建有向图的邻接矩阵inti,j,k,w;charv1,v2;printf(请输入顶点数和边数：);scanf(%d%d,&G.vexnum,&G.arcnum);printf(\n请按次序输入%d个顶点字母标号(如ABCD等)：,G.vexnum);getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for(i=0;iG.vexnum;i++)scanf(%c,&G.vexs[i]);getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for(i=0;iG.vexnum;++i)//初始化邻接矩阵for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}printf(\n输入边的顶点和权值(如AB1):\n);//构造邻接矩阵for(k=0;kG.arcnum;k++){scanf(%c%c%d,&v1,&v2,&w);//输入一条有向边的起点终点和权值6i=LocateVex(G,v1);//确定顶点在G中的位置j=LocateVex(G,v2);G.arcs[i][j].adj=w;getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键}returnOK;}StatusPrintArcs(MGraph&G){//输出邻接矩阵inti;intj;printf(邻接矩阵\n);//按行序依次输出for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++){if(INFINITY==G.arcs[i][j].adj)printf(%6s%,INF);elseprintf(%6d,G.arcs[i][j]);}printf(\n);}returnOK;}StatusShortestPath_DIJ(MGraphG,intv0,intp[],intD[]){//求有向网G的V0到其余顶点的最短路径P[v]及其带权长度D[v]//若p[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点//final[v]为TRUE当且仅当v∈S，即已经求得从v0到v的最短路径intm,v,i,w,j,k;intmin;intfinal[MAX_VERTEX_NUM];chara[MAX_VERTEX_NUM];for(v=0;vG.vexnum;++v){final[v]=FALSE;p[v]=FALSE;D[v]=G.arcs[v0][v].adj;}//forD[v0]=0;final[v0]=TRUE;//初始化，v0属于S7//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集for(i=1;iG.vexnum;++i){min=INFINITY;for(w=0;wG.vexnum;++w)if(!final[w])//w顶点在V-S中if(D[w]min){k=w;min=D[w];}//w离v0更近final[k]=TRUE;for(w=0;wG.vexnum;++w)//更新当前最短路径及距离if(!final[w]&&(min+G.arcs[k][w].adjD[w])){D[w]=min+G.arcs[k][w].adj;p[w]=k;}//if}//forprintf(dijkstra(%c):\n,G.vexs[v0]);for(i=0;iG.vexnum;i++){printf(最短路径长度(%c,%c)=%d\n,G.vexs[v0],G.vexs[i],D[i]);printf(最短路径为：);m=i;j=0;while(m!=v0){a[j]=G.vexs[m];m=p[m];j++;}a[j]=G.vexs[v0];for(m=j;m=0;m--){printf(%c,a[m]);}printf(\n);}returnOK;}voidmainmenu()//输出菜单,供用户进行操作选择{printf(\n菜单);printf(*1.创建有向图邻接矩阵*\n);printf(*2.输出邻接矩阵*\n);8printf(*3.从某点开始到各点的最短路径*\n);printf(*0.退出*\n);}voidmain()//主函数{MGraphG;intchoose;intv0;intp[MAX_VERTEX_NUM]={0};intD[MAX_VERTEX_NUM]={0};while(1){mainmenu();printf(\n请输入你的选择：);scanf(%d,&choose);switch(choose){case1://在此插入创建有向图邻接矩阵函数system(cls);CreateDG(G);system(PAUSE);system(cls);break;case2://在此插入输出邻接矩阵函数system(cls);PrintArcs(G);printf(\n);system(PAUSE);system(cls);break;case3://在此调用从某点开始从某点开始到各点的最短路径求解函数system(cls);printf(请输入开始结点：);scanf(%d,&v0);ShortestPath_DIJ(G,v0,p,D);system(PAUSE);system(cls);break;case0://退出9exit(0);break;default://输入非法，提示用户重新输入printf(\n输入错误，重新输入！\n);}}}