数据结构实验十

一、实验目的

1.使学生熟悉最短路径算法实现。 2.掌握带权图的存储结构和处理方法。二、实验环境

1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； 2.软件：DOS或Windows操作系统+Turbo c;

三、实验要求

1.能够完成带权图的存储和最短路径的生成。

四、实验内容

1.现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。

2.现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra算法实现我的要求的路径。

五、代码如下

#include #include typedef struct{

int *vexs; int **arcs; int vexnum; }ylx_graph ; typedef struct{

int adjvex; int lowcost; }ylx_markedg ;

ylx_graph *ylx_initgraph (){

int i,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;ivexnum;i++)

g->arcs[i]=(int*)malloc(g->vexnum*sizeof(int));

for(i=0;ivexnum;i++) for(j=0;jvexnum;j++){

g->arcs[i][j]=0;}

return g;

}

void ylx_creategraph (ylx_graph *g){

int i,j;

for(i=0;ivexnum;i++)g->vexs[i]=i; g->arcs[0][9]=12; 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;ivexnum;i++) for(j=i;jvexnum;j++) if(g->arcs[i][j])

g->arcs[j][i]=g->arcs[i][j];} void ylx_printgraph (ylx_graph *g){

int x,y;

printf(\"\\n城市间连通图为:\\n\"); for(x=0;xvexnum;x++) for(y=x;yvexnum;y++) if(g->arcs[x][y])printf(\"(%d,%d)距

离:%d\\}

int ylx_selectnearvex (ylx_markedg *mark,int *flag,int num){

int j; int nearestv; int lowcost=32767; for(j=0;j{

nearestv=j;

lowcost=mark[j].lowcost;}} flag[nearestv]=1; return nearestv; } void

ylx_markothervex

(ylx_graph *g,ylx_markedg *mark,int

nearestv,int

num,int*flag){ int j; for(j=0;jif(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;}}}} } void ylx_shortestpath

(ylx_graph

*g,ylx_markedg *mark,int start){

int i,num;

int *flag; int nearestv; num=g->vexnum;

flag=(int *)malloc((num)*sizeof(int)); flag[start]=1; for(i=0;ivexnum;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;ivexnum;i++){

nearestv=ylx_selectnearvex (mark,flag,num); ylx_markothervex (g,mark,nearestv,num,flag);} } void

ylx_printshortpath

(ylx_graph

*g,ylx_markedg *mark,int start){

int i,j,k,path[25]; for(i=0;ivexnum;i++){

if(i!=start){

printf(\"从%d到%d最短路径为:%d;

\ printf(\"途经:\"); k=0;path[k]=i; j=mark[i].adjvex; while(j!=start){ path[++k]=j;

j=mark[j].adjvex;

}

printf(\"%d\

for(j=k;j>=0;j--)printf(\ printf(\".\\n\");}}} void main(){ int city;

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\

ylx_shortestpath (g,mark,city); ylx_printshortpath (g,mark,city); }

六、运行结果截图