校园站点网最短路径的分析与实现

《校园站点网最短路径的分析与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、重庆邮电大学课程论文论文题目：校园站点网最短路径的分析与实现学生姓名：叶强学号：S100202011学院：计算机学院专业：计算机软件与理论指导老师：蒲兴成时间：2010年12月6日第12页（共12页）校园站点网最短路径的分析与实现重庆邮电大学计算机科学院研究生2010级2班叶强S100202011指导老师蒲兴成中文摘要：最短路径问题是图论研究中的一个经典算法问题，旨在寻找图中任意两结点之间的最短路径。本文介绍了图论中求解最短路径的的Dijkstra算法，分析与实现了校园站点网最短路径的求解方法。关键词：图论；Dijkstra；校园；最短路径；VC++第12页（共12页）CampusSite

2、sNetworkAnalysisandImplementationoftheshortestpathAuthorYeQiangInstructorPuXingchengAbstract：Shortestpathproblemisthestudyofgraphtheoryproblemofaclassicalalgorithmtofindanytwographtheshortestpathbetweennodes.ThispaperintroducesgraphtheorytosolvetheDijkstrashortestpathalgorithm,analysisandimplement

3、ationofthecampussitenetworkmethodforsolvingtheshortestpath.Keywords：graphtheory、dijkstra、campus、shortestpath、vc++第12页（共12页）目录一、序言5二、需求分析51、校园站点网模型的建立52、功能需求6三、详细设计及编码61、设计目标62、校园站点网的设计及主要实现函数63、最短路径的算法设计及主要实现函数6（1）Dijkstra算法设计6（2）最短路径的主要实现函数7四、运行结果及分析71、运行步骤及效果图72、结果分析10（1）最短路径的分析10（2）算法时间复杂度的分析11

4、五、结论111、设计的主要成果112、设计中的不足12六、感谢12参考文献12第12页（共12页）一、序言近年来，由于国家政策的允许，一些院校纷纷合并；随着“211工程”的进展，许多高校正在或即将改造、扩建老校区或兴建新校区，校园道路变得错综复杂。再加上学校后勤社会化、服务化，校园里出现了饮食、医疗、百货、洗浴等服务行业，使学校成为一个小型城市，这给学校的管理带来很大的困难。寻找两个地点之间的道路，确定一条从一个位置到另一个位置的最短路径尤其重要[5]。二、需求分析1、校园站点网模型的建立求图的最短路径问题包括两点：一是求图中某一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径

5、。通常的最短路径算法，往往是建立在抽象的数学模型之上，即网络模型。要对校园道路网进行最短路径的分析，首先必须将现实中的校园道路网实体化为网络图论理论中的网络图。在这种网络模型上，实际的路径被抽象为网络中的一条边，实际路径的长度与网络边的长度可以不成比例，以边的权值来表征路径的特征，例如路径的长度、路径步行所耗时间等[7]。校园站点网是一个无向加权连通图，一个顶点表示一个站点，顶点之间的边表示这两个站点之间有道路相连，边上的权值表示连接这两个站点之间的道路的长度[6]。以重庆邮电大学为例，建立校园站点网如图2.1所示。437数图门口口二教学楼口225610新校门口口中心食堂口第12页（共12

6、页）4校车起点点信科大厦口图2.1重庆邮电大学校园站点网2、功能需求针对设计好的重庆邮电大学校园站点网，能求出每对站点间的最短路径长度及最短路。假设图2.1中的站点集合{“新校门口”，“数图门口”，“校车起点”，“二教学楼”，“信科大厦”，“中心食堂”}对应点集合{a，b，c，d，e，z}，现在要求从结点a到z的最短路径。三、详细设计及编码1、设计目标校园站点网最短路径的实现主要用到的技术有VC++6.0[4]，基于框架类的应用程序设计[3]。设计目标是，在确保算法的正确性和效率的前提下，算法应当具有较好的可读性和可理解性，以及容易测试的特点。2、校园站点网的设计及主要实现函数（1）画出校

7、园站点网中所有连通的路线，实现函数为：CPointCMap::GetPosition(intcol,introw)voidShowMap(CDC*pDC)voidInitPath()（2）画出校园站点网中所有站点，实现函数为：CStation(intcol,introw,LPCSTRname,CMap&map)voidShowStation(CDC*pDC)（3）画出所有显示信息的矩形框，包括站点间的长度，选择站点，重新