数据结构最短路径.doc

图的最短路径
一、 实验目的
1. 使学生熟悉最短路径的算法实现
二、 掌握带权图的存储结构和处理方法
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;
}graph_hc;

typedef struct
{int adjvex;
int lowcost;
}markedg_hc;

graph_hc*initgraph_hc()
{int i,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;i<g->vexnum;i++)
g->arcs[i]=(int*)malloc(g->vexnum*sizeof(int));
for(i=0;i<g->vexnum;i++)
for(j=0;j<g->vexnum;j++)
{g->arcs[i][j]=0;}
return g;}

void creategraph_hc(graph_hc *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 printgraph_hc(graph_hc*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 selectnearvex_hc(markedg_hc*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 markothervex_hc(graph_hc*g,markedg_hc*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].lowcost+g->arcs[nearestv][j]))
{mark[j].lowcost= mark[nearestv].lowcost+g->arcs[nearestv][j];
mark[j].adjvex=nearestv;}}}}}

void shortestpath_hc(graph_hc*g,markedg_hc*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=selectnearvex_hc(mark,flag,num);
markothervex_hc(g,mark,nearestv,num,flag);}}

void printshortpath_hc(graph_hc*g,markedg_hc*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");}}}

main()
{int city;
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作者:黄晨");}