数据结构_图的最短路径实现

1、数据结构实验课程名称数据结构实验题目名称图的最短路径实现学生学院应用数学学院专业班级信息计算1班学号3114008104学生姓名陈辉腾指导教师刘志煌2016年6月13日图的最短路径实现14信计1班一陈辉腾一3114008104实验要求：广东省主要大城市之间的交通图如下所示，每条边上的权值代表从城市A到城市B的路途长度，使用数据结构图的相关理论编程给出广州到各个城市的最短路径，并且输出经过的路径。实验目的：进一步了解数据结构中对图的各种操作，以及求最短路径的算法。实验内容：编程求解上述题目（实验要求）思路：首先把图用带权邻接矩阵g表示出来（每个城市看做一个顶点，广州是v0）,然后用c语言实现书上

2、的迪杰斯特拉算法，求有向网g的v0顶点到其余顶点v的最短路径保存到Dv,以及途经的一个最近新的路径保存Pathv。最后输出Dv以及Pathv。构造领接矩阵代码如下（详细思路写在代码注释里面）：其中:（v0是广州；v1是佛山；v2是肇庆；v3是珠海；v4是深圳；v5是南宁；v6是香港）数据类型定义：全局的圉）vCreate-DNfMGrapSinclude<stdlih.h）INF1000"最大值无交ifdefineHAX.VE艮tEXJO7最大顶点数Qiypedefenuff）GD5fUDG,皿用Gt叩hKind;"有向图，有网图，无向图，无网图1ypedefstIn

3、foType：7弧相关信息变型“融相关信息的指钟-typedefcharVeHei<Typ&/顶点费据类理iypedefirtVRTyp引“顶点关系类型。时无权图，用。或者1表示是否相郃。对帝权图，直接表示权值。三type品fstructArcCellTRTypeadj;顶点关器类型，对无权图，用。或者1表示是否相邻对带松图，直掩表示权值InfoType朽.时。强相关信息的指针ElAdjUatrisMAX_VERTEK_MUlffW_VERTEK_IOI：-typedefstructITertesTypew菖MA:讪RTEXJiim顶点向里AdjustrixM:邻楚施隧int5k

4、皿eJTina:“顶点数范数aphKindkiitd;EllMGraph;构造上述领接矩阵函数代码:FintGreateDNWraphFortini=0：1<M<_VERTEK_MUM：1+4)(foitint三口：j<MX_VERTEX_NIIN：j+)ff.Hljadj=IMF:MijLadj=0:s.Wl0l.adj=10D；c,I0.adj200；s,I03,ad>200；g.I13.adj=&0；g.M14,adj=1E0;gJT23.adj=100;g.I25.adj=150：e.I34.adj=inO：e,I35,adj=360：g.M4S.adj

5、=lED；g.M64.adj=400；.ME6.adj=E00;eNwiL=UlX_VERTEX_NUM;charc=r#r;psnlfC有向网帚板邻接矩阵为t,取代襄无究大：pnntf-广州佛山擎庆珠海聚圳南宁香港5")；for(inik=0;k<eNum;k+)for(int1=0;l<gkeNiin;1+)if(S.M|>1.adj1=1000)printfC%5dn,g.15k1.adj)；gL占号prirrtfC愤5cg);printErn；printfrnn；return1;广州佛山8100it运行结果如下:C:Windowssystm32cmdEewe

6、有向网带权邻接矩阵为（代表无穷大），肇庆珠海深圳南宁香港2002S0ttittt50tt350Ittt1S0ii430tt请按任意键继续求最短距离和路径函数如下:全局范勖-voidShorteitPath(HCr3phi,iritvO)intcotMAX=1M_VERTEX_NUM：intSMAX>3I时意底着保存了最终M至必的最短路径intDUUK："最短距离intPrthEMAX:若F3rthi=>表示vO->e的最短距离的施役包含受力而且行一直保持轼更新状态，输出路径时就要用到潴归。£1(intB。；*g.gNum;+%)/初帕比SM=T;S集里面设

7、为空Dv=酊肌娅利.冢；“姮陡篥一行(即vO到其他点的直接距离)麟给DU;if(Dv<rNF)Pa±hv=式!：，/，速为空elsePatliv=11Dv3=O;Path.vO=0;SvO=1;/旬加入二集“开始主循环每次求得诃到其他顶点守的最姮路径，并加唔胆隼for(ifft1-1;J-g.tNum;t-M")liftv;mtnin=INF；/7min保存当前所知离M顶点最近的距离for(mtw=0；¥<g.sKujil;w+)if(SM=T)/7呐顶点不在S里ifw5in)v=w；/记下当前最短距离的位置in=Dw修改肌in)SM=l；M入瞧fcr

8、(intt=0:v<g»&Kuji:w+)if<Svl=-1也量(min十g.Hfvw*adj<Dv)Dw=min.+g,Mvw,ad：</修改当H辰短距离PathM=也"保存下途经路径，并随时更新|输出最想即离i.=0：iQ.eNu：T-I-+)if(Di=1000)ptintf(“广州至I")-mi):psntf的最姮距离为；无穷大tn");elsep嵋出广州到U；Set:pH毗的量也题离为：塌5二。【口上输出Prthprintft“path：").ior(Lnti=0;ig,eNum;i+)prijitfC

9、JSSd"jPathfil);prirrtffVi"):输出路轻fortinti=0：iCg.elluin：i+)ifCSCil=l廉i>=rO)printfC从广州到");SetFaae(i);printf("的最短距离的路径为：广州-二)二"起点FassPathffath,:"经路径|SetJIame(i)：printfCXn"):终点«i''ir其中，PassPath(Path,i,v0)函数实现如下：日输出路径困数如公式的最短路径途经C，而7。的最短路径途经h那其实的最短路径同时途经b

10、和h而根据d只能蹲到一个i(HI"靛只能求出G。现在也要求出b来，只能通过G来束，所以形成了递归。v&idPa?Fath(intpjinXLintv)inti=Pi.Ilf(k=v)return;"直达，无SS径，FassPath(pJkJv);递归i局用SetName(k);prizrtfC-*);1SetName(i)函数(根据矩阵的行列数i,获得对应的城市名)实现如下:L-voidSeiNametinti)ETitch(i)case0：riutf("广州breal;case1:r工iritf("佛山")；br巧疝:case2:卫r

11、irrtfC"肇庆：brgik:case3:printf(")：brealt：case4:pzrintf("深Ull');break;case5:j)rintfCMT");breaJ?;esseS:pidzutfCSS)；运行求解结果为:tt港清海如II-珠深南深>>77一一二山庆山山庆山im>>>>>>-tut1-JrJ-JJ-zJ71-JrJ/广广广广广广0000004H133S二sa01212342KSS8ES为为为为为为为士离离离离离离-一置局离离一&何-n-n-rl-Ln=n-n-

12、一巨巨巨巨巨巨1nsninTKnxRnfnxR-.江-r-r-.o丝H一0f®>>ft-口瞽譬瞽瞽国曾取0的的的的的的的的的的的的山庆海圳矗®州山灰海/,-IIE0嚏聿或深南寮广羹笠林目-日到意j扑扑力外扑升任广广广州X广广广广广广技总结：一开始觉得图的好难，不过，确实很难啊，图比树复杂多了。其实还有一部分原因是自己对图比较陌生的缘故吧。对于这个求最短路径的算法的难点，个人觉得是在输出路径那里，巧妙的用到了递归。还有我觉得，怎么把巧妙的吧途经最短路径保存下来？处理这个问题我就觉得是一个难点，把这个问题处理的好，输出时就比较不用那么麻烦。书本是用一个二维数组p田和

13、一个一维数组p口来处理，两个数组名还一样，个人不太懂一最后面一行没看懂，就是：pw=pv;pww=TRUE;/pw=pv+w,书本也没有对其路径的输出做处理，我也没有深究下去，而是参考别的资料采用另一种方法来处理（不过都是差不多的吧）。总的来说，个人觉得输出路径的函数PassPath()很经典。另外一开始看不懂书本上的算法就感觉好打击，后来就分析算法后面的运行情况，上机调试，慢慢的就基本明白了。算法实现后，就是要解决给用户的体验效果了，这个就不难，仅做简单处理，写了一个简单的SetName()函数(名字取得不太好，应该叫GetName(),然后选择适当的时候输出适当的话或城市名就行了。附录：(

14、代码)头文件部分：#include<stdlib.h>#defineINF1000/最大值无穷#defineMAX_VERTEX_NUM7/最大顶点数typedefenumDG,DN,UDG,UDNGraphKind;/有向图，有网图，无向图，无网图typedefintInfoType;/弧相关信息类型弧相关信息的指针typedefcharVertexType;/顶点数据类型typedefintVRType;/顶点关系类型。对无权图，用。或者1表示是否相邻。对带权图，直接表示权值。typedefstructArcCellVRTypeadj;/顶点关系类型，对无权图，用。或者1表示是

15、否相邻。对带权图，直接表示权值InfoType*info;/弧相关信息的指针AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;/顶点向量AdjMatrixM;/邻接矩阵intvNum,eNum;/顶点数弧数GraphKindkind;MGraph;intCreateDN(MGraph&g)for(inti=0;i<MAX_VERTEX_NUM;i+)for(intj=0；j<MAX_VERTEX_NUM；j+)g.M皿.adj=INF;if(i=j)g.Mij.ad

16、j=0;g.M01.adj=100;g.M02.adj=200;g.M03.adj=200;g.M13.adj=50;g.M14.adj=150;g.M23.adj=100;g.M25.adj=150;g.M34.adj=100;g.M35.adj=350;g.M46.adj=150;g.M54.adj=400;g.M56.adj=500;g.vNum=g.eNum=MAX_VERTEX_NUM;charc='#'printf("有向网带权邻接矩阵为(#代表无穷大)：nn");printf("广州佛山肇庆珠海深圳南宁香港n");for(i

17、ntk=0;k<g.eNum;k+)for(intl=0;l<g.eNum;l+)if(g.Mkl.adj!=1000)printf("%5d",g.Mkl.adj);elseprintf("%5c",c);printf("n");printf("n");return1;源文件部分：#include<stdio.h>#include"ShortestPath.h"voidSetName(inti)switch(i)case0:printf("广州");

18、break;case 1 :printf("佛山");break;case 2 :printf("肇庆");break;case 3 :printf("珠海");break;case 4 :printf("深圳");break;case 5 :printf("南宁");break;case 6 :printf("香港”)；/输出路径函数，如a->d的最短路径途经c,而a->c的最短路径途经b,那其实a->d的最短路径同时途经了b和co而不g据d只能得到一个i(k)/故

19、只能求出Co现在也要求出b来，只能通过c来求，所以形成了递归。voidPassPath(intp,inti,intv)intk=pi;if(k=v)return;/直达，无路径。PassPath(p,k,v);/递归调用SetName(k);printf("->");voidShortestPath(MGraphg,intv0)intconstMAX=MAX_VERTEX_NUM;intSMAX;/S集-，为1时意味着保存了最终v0到v的最短路径intDMAX;/最短距离intPathMAX;/若Pathi=j,表示v0->vi的最短距离的路径包含vj。/而且v

20、j一直保持被更新状态，输出路径时就要用到递归。for(intv=0;v<g.eNum;+v)/初始化Sv=-1;/S集里面设为空Dv=g.Mv0v.adj;/矩阵第一行(即v0到其他点的直接距离)赋给D口;if(Dv<INF)Pathv=v0;/路径设为空elsePathv=-1;Dv0=0;Pathv0=0;Sv0=1;/v0加入S集开始主循环，每次求得v0到其他顶点v的最短路径，并加v到S集for(inti=1;i<g.eNum;i+)intv;intmin=INF;/min保存当前所知离v0顶点最近的距离for(intw=0;w<g.eNum;w+)if(Sw=-1)/w顶点不在S里if(Dw<min)v=w;/记下当前最短距离的位置min=Dw;/修改min)Sv=1;/加入S集f