欢迎来到冰点文库! | 帮助中心 分享价值,成长自我!
冰点文库
全部分类
  • 临时分类>
  • IT计算机>
  • 经管营销>
  • 医药卫生>
  • 自然科学>
  • 农林牧渔>
  • 人文社科>
  • 工程科技>
  • PPT模板>
  • 求职职场>
  • 解决方案>
  • 总结汇报>
  • ImageVerifierCode 换一换
    首页 冰点文库 > 资源分类 > DOCX文档下载
    分享到微信 分享到微博 分享到QQ空间

    《数据结构课程设计》最短路径问题实验报告Word下载.docx

    • 资源ID:8278909       资源大小:180.54KB        全文页数:15页
    • 资源格式: DOCX        下载积分:3金币
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录
    二维码
    微信扫一扫登录
    下载资源需要3金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP,免费下载
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    《数据结构课程设计》最短路径问题实验报告Word下载.docx

    1、邻接矩阵就是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)就是具有n个顶点的图,则G的邻接矩阵就是具有如下定义的n阶方阵。注:一个图的邻接矩阵表示就是唯一的!其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息(下标为i的元素存储顶点的信息)。邻接矩阵的存储结构:#define MVNum 100 /最大顶点数typedef struct VertexType vexsMVNum;/顶点数组,类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵,假定为int型MGraph;由于有向图的邻接矩阵就是不对称的,

    2、故程序运行时只需要输入所有有向边及其权值即可。4、2单源最短路径单源最短路径问题:已知有向图(带权),期望找出从某个源点SV到G中其余各顶点的最短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想:设有向图G=(V,E),其中V=1,2,n,cost就是表示G的邻接矩阵, costij表示有向边的权。若不存在有向边,则costij 的权为无穷大(这里取值为32767)。设S就是一个集合,集合中一个元素表示一个顶点,从源点到这些顶点的最短距离已经求出。设顶点V1为源点,集合S的初态只包含顶点V1。数组dist记录从源点到其它各顶点当前的最短距离,其初值为disti= cost

    3、ij,i=2,n。从S之外的顶点集合V-S中选出一个顶点w,使distw 的值最小。于就是从源点到达w只通过S中的顶点,把w加入集合S中,调整dist中记录的从源点到V-S中每个顶点v的距离:从原来的distv与distw+costwv中选择较小的值作为新的distv。重复上述过程,直到S中包含V中其余顶点的最短路径。 最终结果就是:S记录了从源点到该顶点存在最短路径的顶点集合,数组dist记录了从源点到V中其余各顶点之间的最短路径,path就是最短路径的路径数组,其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。4、3任意一对顶点之间的最短路径 任意顶点对之间的最短路径问题,就是对于

    4、给定的有向网络图G=(V,E),要对G中任意一对顶点有序对,“V,W(VW)”,找出V到W的最短路径。而要解决这个问题,可以依次把有向网络图中每个顶点作为源点,重复执行前面的迪杰斯特拉算法n次,即可求得每对之间的最短路径。 费洛伊德算法的基本思想:假设求从Vi到Vj的最短路径。如果存在一条长度为arcsij的路径,该路径不一定就是最短路径,还需要进行n次试探。首先考虑路径与就是否存在。如果存在,则比较路径vi,v1,vj的路径长度,取长度较短者为当前所求得。该路径就是中间顶点序号不大于1的最短路径。其次,考虑从vi到vj就是否包含有顶点v2为中间顶点的路径,若没有,则说明从vi到vj的当前最短

    5、路径就就是前一步求出的;若有,那么可分解为v2,vj,而这两条路径就是前一次找到的中间点序号不大于1的最短路径,将这两条路径长度相加就得到路径的长度。将该长度与前一次中求得的从vi到vj的中间顶点序号不大于1的最短路径比较,取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推直至顶点vn加入当前从vi到vj的最短路径后,选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n,所以vi到vj的中间顶点序号不大于n的最短路径,已考虑了所有顶点作为中间顶点的可能性,因此,它就就是vi到vj的最短路径。五、运行与测试测试实例1:利用如下图所示的有

    6、向图来测试测试实例2:利用下图求交通网络图(无向图)的最短路径。实例1运行结果:实例2运行结果:六、总结与心得该课程设计主要就是从日常生活中经常遇到的交通网络问题入手,进而利用计算机去建立一个交通咨询系统,以处理与解决旅客们关心的各种问题(当然此次试验最终主要解决的问题就是:最短路径问题)。这次试验中我深刻的了解到了树在计算机中的应用就是如何的神奇与灵活,对于很多的问题我们可以通过树的相关知识来解决,特别就是在解决最短路径问题中,显得尤为重要。经过着次实验,我了解到了关于树的有关算法,如:迪杰斯特拉算法、弗洛伊德算法等,对树的学习有了一个更深的了解。参考文献【1】数据结构严蔚敏、清华大学出版社

    7、、【2】数据结构课程设计苏仕华、极械工业出版社、附录#includestdlib、h#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structint D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph(MGraph * G,int n,int e) int i,j,k,w; for(i=1;ivexsi=(char)i; for(j=1;jar

    8、csij=Maxint; printf(输入%d条边的i、j及w:n,e); for(k=1;k=e;k+) scanf(%d,%d,%d,&i,&j,&w);arcsij=w; 有向图的存储结构建立完毕!);void Dijkstra(MGraph *G,int v1,int n) int D2MVNum,p2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;varcsv1v; if(D2vMaxint) p2v=v1; else p2v=0; D2v1=0; Sv1=TRUE; for(i=2;n;i+) min=Maxint; for(

    9、w=1;ww+) if(!Sw & D2warcsvwarcsvw; p2w=v; printf(路径长度 路径n%5d,D2i);,i);v=p2i; while(v!=0) printf(arcsij!=Maxint) pij=j; else pij=0; Dij=G-arcsij;k+) for(i=1; for(j=1; if(Dik+DkjDij) Dij=Dik+Dkj; pij=pik; void main() MGraph *G; int m,n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph);输入图中顶点个数与边数n,

    10、e: scanf(%d,%dn,&e); CreateMGraph(G,n,e); while(xz!*求城市之间最短路径*n=n1、求一个城市到所有城市的最短路径n2、求任意的两个城市之间的最短路径n请选择 :1或2,选择0退出:%dxz); if (xz=2) Floyd(G,n); printf(输入源点(或起点)与终点:v,w: scanf(v,& k=pvw; if (k=0) printf(顶点%d 到 %d 无路径!,v,w); else从顶点%d 到 %d 最短路径路径就是:,v,w,v); while (k!=w) printf(-%d,k); k=pkw;,w);径路长度:%dn,Dvw); if(xz=1)求单源路径,输入源点v :v); Dijkstra(G,v,n);结束求最短路径,再见!


    注意事项

    本文(《数据结构课程设计》最短路径问题实验报告Word下载.docx)为本站会员主动上传,冰点文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知冰点文库(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    copyright@ 2008-2023 冰点文库 网站版权所有

    经营许可证编号:鄂ICP备19020893号-2


    收起
    展开