数据结构最短路径

1、图的最短路径1、 实验目的1. 使学生熟悉最短路径的算法实现2、 掌握带权图的存储结构和处理方法1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows2. 软件：DOS或Windows操作系统+Turbo C;3、 实验要求1. 能够独立完成带权图的存储和最短路径的生成4、 实验内容1. 现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。2. 现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra算法实现我的要求的路径。#include stdio.h#include malloc.htypedef structint

2、*vexs; int *arcs; int vexnum;graph_hc;typedef structint 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;ivexnum;i+)g-arcsi=(int*)malloc

3、(g-vexnum*sizeof(int);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)g-arcsij=0;return g;void creategraph_hc(graph_hc *g)int i,j; for(i=0;ivexnum;i+)g-vexsi=i;g-arcs09=1892; g-arcs13=242; g-arcs24=668; g-arcs29=1145; g-arcs35=305; g-arcs46=137; g-arcs411=695; g-arcs56=704; g-arcs57=397; g-arcs612=674; g-arcs

4、89=216; g-arcs910=676;g-arcs1011=511;g-arcs1013=842;g-arcs1112=349;g-arcs1114=534;g-arcs1215=651;g-arcs1316=110;g-arcs1317=967;g-arcs1418=409;g-arcs1519=825;g-arcs1617=639;g-arcs1718=902;g-arcs1721=607;g-arcs1819=367;g-arcs1821=672;g-arcs1823=675;g-arcs1920=622;g-arcs2122=255;g-arcs2324=140;for(i=0;

5、ivexnum;i+) for(j=i;jvexnum;j+) if(g-arcsij)g-arcsji=g-arcsij;void printgraph_hc(graph_hc*g)int x,y;printf(n城市间连通图为:n);for(x=0;xvexnum;x+)for(y=x;yvexnum;y+)if(g-arcsxy)printf(%d,%d)距离:%dt,x,y,g-arcsxy);int selectnearvex_hc(markedg_hc*mark,int *flag,int num)int j;int nearestv;int lowcost=32767;for(j

6、=0;jnum;j+)if(flagj!=1&markj.lowcostlowcost)nearestv=j;lowcost=markj.lowcost;flagnearestv=1;return nearestv;void markothervex_hc(graph_hc*g,markedg_hc*mark,int nearestv,int num,int*flag)int j;for(j=0;jarcsnearestvj0)if(flagj!=1)if(markj.lowcost(marknearestv.lowcost+g-arcsnearestvj)markj.lowcost= mar

7、knearestv.lowcost+g-arcsnearestvj;markj.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);flagstart=1;for(i=0;ivexnum;i+)marki.adjvex=start;if( g-arcsstarti0)marki.lowcost=g-arcsstarti;elsemarki

8、.lowcost=32767;for(i=1;ivexnum;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,path25;for(i=0;ivexnum;i+)if(i!=start)printf(从%d到%d最短路径为:%d; ,start,i,marki.lowcost);printf(途经:);k=0;pathk=i;j=ma

9、rki.adjvex;while(j!=start)path+k=j;j=markj.adjvex;printf(%d,start);for(j=k;j=0;j-)printf(,%d,pathj);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=(marked