欢迎来到天天文库
浏览记录
ID:39392613
大小:131.61 KB
页数:9页
时间:2019-07-02
《深基坑工程7-地下水控制2》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、校园导游程序分析1设计校园平面图,所含景点不少于10个。以图中顶点表示学校各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。要求:为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径;为来访客人提供图中景点间的推荐路线(遍历各节点的最短路线)和各景点之间的介绍。21.问题描述华科校园景点图信息503230402040404026252039100101020301.南大门广场2.光谷体育馆3.眼镜湖4.紫松8.东九…9.瑜园10.珞珈山11.韵苑12.爱因斯…7
2、.光电…5.青年园6.集贸市场3输出格式要求顺序打印景点和介绍,格式要求:STEP1:景点名景点介绍两个景点间打印两景点距离和已走距离:DISTANCE:XXXandTRAVELLED:XXX最后打印总的路程长度:TOTAL:XXX4节点组成无向图,则可用最短路径求解:Dijkstra算法(时间复杂度0(n2))采用Dijkstra算法,每次对路径的查询都需要进行相应的计算。2.Floyd算法(时间复杂度为0(n3)但若采用Floyd算法,在第一次进行路径查询前进行相应的计算后,在图信息不变的前提下,不需要再次进行计
3、算。52.解析voidfloyed(){inti,j,k;for(i=1;i(shortest[i][k]+shortest[k][j])){shortest[i][j]=shortest[i][k]+shortest[k][j];pa
4、th[i][j]=k;}}6Floyd算法7通过中转矩阵来得到最短路径voidppath(inti,intj)//得到i到j最短路径的中间节点号{intk=path[i][j];if(k==0)return;//表示i和j之间没有可以中转的结点ppath(i,k);//递归调用pathArray[count]=k;//pathArray用来顺序存放中间节点count++;ppath(k,j);}8Floyd算法的中转矩阵图9谢谢观赏
此文档下载收益归作者所有