数据结构最短路径

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

2、quot;malloc.h"typedef structint *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->ve

3、xnum*sizeof(int*);for(i=0;i<g->vexnum;i+)g->arcsi=(int*)malloc(g->vexnum*sizeof(int);for(i=0;i<g->vexnum;i+)for(j=0;j<g->vexnum;j+)g->arcsij=0;return g;void creategraph_hc(graph_hc *g)int i,j; for(i=0;i<g->vexnum;i+)g->vexsi=i;g->arcs09=1892; g->arcs13=242;

4、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->arcs89=216; g->arcs910=676;g->arcs1011=511;g->arcs1013=842;g->arcs1112=349;g->arcs1114=534;g->arcs1215=651;g->arcs1316=110;g-&

5、gt;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;i<g->vexnum;i+) for(j=i;j<g->vexnum;j+) if(g->arcsij

6、)g->arcsji=g->arcsij;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->arcsxy)printf("(%d,%d)距离:%dt",x,y,g->arcsxy);int selectnearvex_hc(markedg_hc*mark,int *flag,int num)int j;int nearestv;int l

7、owcost=32767;for(j=0;j<num;j+)if(flagj!=1&&markj.lowcost<lowcost)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;j<num;j+)if(g->arcsnearestvj>0)if(flagj!=1)if(markj.lowc

8、ost>(marknearestv.lowcost+g->arcsnearestvj)markj.lowcost= marknearestv.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;i<g-&g

9、t;vexnum;i+)marki.adjvex=start;if( g->arcsstarti>0)marki.lowcost=g->arcsstarti;elsemarki.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,path25

10、;for(i=0;i<g->vexnum;i+)if(i!=start)printf("从%d到%d最短路径为:%d; ",start,i,marki.lowcost);printf("途经:");k=0;pathk=i;j=marki.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()in

11、t 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->vex