一、实验目的
1.使学生熟悉最短路径算法实现。
2.掌握带权图的存储结构和处理方法。
二、实验环境
1.硬件：每个学生需配备计算机一台。
操作系统：DOS或Windows；
2.软件：DOS或Windows操作系统+Turbo c;
三、实验要求
1.能够独立完成带权图的存储和最短路径的生成。
四、实验内容
1.现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。
2.现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra算法实现我的要求的路径。
五、代码如下
#include <stdio.h>
#include <malloc.h>
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;i<g->vexnum;i++)
g->arcs[i]=(int*)malloc(g->vexnum*sizeof(in t));
for(i=0;i<g->vexnum;i++)
for(j=0;j<g->vexnum;j++){
g->arcs[i][j]=0;}
return g;
}
void ylx_creategraph (ylx_graph *g){ int i,j;
for(i=0;i<g->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;i<g->vexnum;i++)
for(j=i;j<g->vexnum;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;x<g->vexnum;x++)
for(y=x;y<g->vexnum;y++)
if(g->arcs[x][y])printf("(%d,%d)距离:%d\t",x,y,g->arcs[x][y]);
}
int ylx_selectnearvex (ylx_markedg *mark,int *flag,int num){
int j;
int nearestv;
int lowcost=32767;
for(j=0;j<num;j++){
if(flag[j]!=1&&mark[j].lowcost<lowcost) {
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;j<num;j++){
if(g->arcs[nearestv][j]>0){
if(flag[j]!=1){
if(mark[j].lowcost>(mark[nearestv].lowc ost+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;i<g->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;i<g->vexnum;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;i<g->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");}}}
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",&city);
ylx_shortestpath (g,mark,city);
ylx_printshortpath (g,mark,city);
}
六、运行结果截图。