数据结构最短路径.doc

图的最短路径
实验目的
使学生熟悉最短路径的算法实现
掌握带权图的存储结构和处理方法
硬件:每个学生需配备计算机一台。操作系统:DOS或Windows
软件:DOS或Windows操作系统+Turbo C;
实验要求
能够独立完成带权图的存储和最短路径的生成
实验内容
现在假设我国铁路交通图如下(权值表示距离),请用合适的存储结构将下图存储到计算机中方便进行处理。
现在我想以最小的代价从徐州出发到达其他目的地,请用Dijkstra算法实现我的要求的路径。
#include ""
#include ""
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][