数据结构实验十

一、实验目的1.使学生熟悉最短路径算法实现。2.掌握带权图的存储结构和处理方法。二、实验环境1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows；2.软件：DOS或Windows操作系统+Turboc;三、实验要求1.能够独立完成带权图的存储和最短路径的生成。四、实验内容1.现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。2.现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra算法实现我的要求的路径。五、代码如下#includestdio.h#includemalloc.htypedefstruct{int*vexs;int**arcs;intvexnum;}ylx_graph;typedefstruct{intadjvex;intlowcost;}ylx_markedg;ylx_graph*ylx_initgraph(){inti,j;ylx_graph*g;g=(ylx_graph*)malloc(sizeof(ylx_graph));g-vexnum=25;g-vexs=(int*)malloc(g-vexnum*sizeof(int));g-arcs=(int**)malloc(g-vexnum*sizeof(int*));for(i=0;ig-vexnum;i++)g-arcs[i]=(int*)malloc(g-vexnum*sizeof(int));for(i=0;ig-vexnum;i++)for(j=0;jg-vexnum;j++){g-arcs[i][j]=0;}returng;}voidylx_creategraph(ylx_graph*g){inti,j;for(i=0;ig-vexnum;i++)g-vexs[i]=i;g-arcs[0][9]=1892;g-arcs[1][3]=242;g-arcs[2][4]=668;g-arcs[2][9]=1145;g-arcs[3][5]=305;g-arcs[4][6]=137;g-arcs[4][11]=695;g-arcs[5][6]=704;g-arcs[5][7]=397;g-arcs[6][12]=674;g-arcs[8][9]=216;g-arcs[9][10]=676;g-arcs[10][11]=511;g-arcs[10][13]=842;g-arcs[11][12]=349;g-arcs[11][14]=534;g-arcs[12][15]=651;g-arcs[13][16]=110;g-arcs[13][17]=967;g-arcs[14][18]=409;g-arcs[15][19]=825;g-arcs[16][17]=639;g-arcs[17][18]=902;g-arcs[17][21]=607;g-arcs[18][19]=367;g-arcs[18][21]=672;g-arcs[18][23]=675;g-arcs[19][20]=622;g-arcs[21][22]=255;g-arcs[23][24]=140;for(i=0;ig-vexnum;i++)for(j=i;jg-vexnum;j++)if(g-arcs[i][j])g-arcs[j][i]=g-arcs[i][j];}voidylx_printgraph(ylx_graph*g){intx,y;printf(\n城市间连通图为:\n);for(x=0;xg-vexnum;x++)for(y=x;yg-vexnum;y++)if(g-arcs[x][y])printf((%d,%d)距离:%d\t,x,y,g-arcs[x][y]);}intylx_selectnearvex(ylx_markedg*mark,int*flag,intnum){intj;intnearestv;intlowcost=32767;for(j=0;jnum;j++){if(flag[j]!=1&&mark[j].lowcostlowcost){nearestv=j;lowcost=mark[j].lowcost;}}flag[nearestv]=1;returnnearestv;}voidylx_markothervex(ylx_graph*g,ylx_markedg*mark,intnearestv,intnum,int*flag){intj;for(j=0;jnum;j++){if(g-arcs[nearestv][j]0){if(flag[j]!=1){if(mark[j].lowcost(mark[nearestv].lowcost+g-arcs[nearestv][j])){mark[j].lowcost=mark[nearestv].lowcost+g-arcs[nearestv][j];mark[j].adjvex=nearestv;}}}}}voidylx_shortestpath(ylx_graph*g,ylx_markedg*mark,intstart){inti,num;int*flag;intnearestv;num=g-vexnum;flag=(int*)malloc((num)*sizeof(int));flag[start]=1;for(i=0;ig-vexnum;i++){mark[i].adjvex=start;if(g-arcs[start][i]0){mark[i].lowcost=g-arcs[start][i];}else{mark[i].lowcost=32767;}}for(i=1;ig-vexnum;i++){nearestv=ylx_selectnearvex(mark,flag,num);ylx_markothervex(g,mark,nearestv,num,flag);}}voidylx_printshortpath(ylx_graph*g,ylx_markedg*mark,intstart){inti,j,k,path[25];for(i=0;ig-vexnum;i++){if(i!=start){printf(从%d到%d最短路径为:%d;,start,i,mark[i].lowcost);printf(途经:);k=0;path[k]=i;j=mark[i].adjvex;while(j!=start){path[++k]=j;j=mark[j].adjvex;}printf(%d,start);for(j=k;j=0;j--)printf(,%d,path[j]);printf(.\n);}}}voidmain(){intcity;ylx_graph*g;ylx_markedg*mark;g=ylx_initgraph();ylx_creategraph(g);printf(城市对应编号:\n);printf(0-乌鲁木齐1-哈尔滨2-呼和浩特3-长春4-北京\n);printf(5-沈阳6-天津7-大连8-西宁9-兰州10-西安11-郑州\n);printf(12-徐州13-成都14-武汉15-上海16-昆明17-贵阳18-株州\n);printf(19-南昌20-福州21-柳州22-南宁23-广州24-深圳.\n);ylx_printgraph(g);mark=(ylx_markedg*)malloc(g-vexnum*sizeof(ylx_markedg));printf(\n输入起始城市:);scanf(%d,&city);ylx_shortestpath(g,mark,city);ylx_printshortpath(g,mark,city);}六、运行结果截图