数据结构最短路径

图的最短路径一、实验目的1.使学生熟悉最短路径的算法实现二、掌握带权图的存储结构和处理方法1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows2.软件：DOS或Windows操作系统+TurboC;三、实验要求1.能够独立完成带权图的存储和最短路径的生成四、实验内容1.现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。2.现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra算法实现我的要求的路径。#includestdio.h#includemalloc.htypedefstruct{int*vexs;int**arcs;intvexnum;}graph_hc;typedefstruct{intadjvex;intlowcost;}markedg_hc;graph_hc*initgraph_hc(){inti,j;graph_hc*g;g=(graph_hc*)malloc(sizeof(graph_hc));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;}voidcreategraph_hc(graph_hc*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];}voidprintgraph_hc(graph_hc*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]);}intselectnearvex_hc(markedg_hc*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;}voidmarkothervex_hc(graph_hc*g,markedg_hc*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;}}}}}voidshortestpath_hc(graph_hc*g,markedg_hc*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=selectnearvex_hc(mark,flag,num);markothervex_hc(g,mark,nearestv,num,flag);}}voidprintshortpath_hc(graph_hc*g,markedg_hc*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);}}}main(){intcity;graph_hc*g;markedg_hc*mark;g=initgraph_hc();creategraph_hc(g);printf(城市名称/代号:);printf(乌鲁木齐/0,哈尔滨/1,呼和浩特/2,长春/3,北京/4,);printf(沈阳/5,天津/6,大连/7,西宁/8,兰州/9,西安/10,郑州/11,);printf(徐州/12,成都/13,武汉/14,上海/15,昆明/16,贵阳/17,株州/18,);printf(南昌/19,福州/20,柳州/21,南宁/22,广州/23,深圳/24.\n);printgraph_hc(g);mark=(markedg_hc*)malloc(g-vexnum*sizeof(markedg_hc));printf(\n输入起始城市:);scanf(%d,&city);shortestpath_hc(g,mark,city);printshortpath_hc(g,mark,city);printf(\n作者:黄晨);}