校园导航系统最短路径的实现_杨伟龙

《校园导航系统最短路径的实现_杨伟龙》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2014年4月韶关学院学报·自然科学Apr.2014第35卷第4期JournalofShaoguanUniversity·NaturalScienceVol.35No.4校园导航系统最短路径的实现杨伟龙，李步德，谢俊鹏（韶关学院档案馆，广东韶关512005）摘要：随着高校的发展，校园面积不断扩大，为适应数字化校园建设的要求，各高校开发设计了校园导航系统.查询最短路径的实现是校园导航系统主要功能之一，阐述了基于Flash技术开发平台，运用迪杰斯特拉（Dijkstra）算法实现校园导航系统最短路径的功能.关键词：高校；导航系统

2、；最短路径；迪杰斯特拉算法中图分类号：TP311.5文献标识码：A文章编号：1007-5348（2014）04-0020-04随着国内高校的发展，校园面积不断扩大.校园内教学楼、办公楼、学生公寓、运动场馆、商业网点、绿化景点等林林总总、错综复杂，即使在学校工作、生活几年的老师或学生也未必清楚了解，对于外来办事的人员更会带来诸多不便.许多高校专门设计了校园电子地图导航系统，为师生和校外人士办事办公提供便利.为适应数字化校园建设的要求，韶关学院也自主开发了一款校园导航系统，系统在用3dsmax构建了本校电子地图的基础上，采用了

3、Flash开发及ActionScript3.0语言，结合PHP+MySQL进行设计，实现了基于Flash［1］技术平台的校园虚拟地图导航系统.最短路径的实现是校园导航系统主要功能之一，用户设定起点和终点，系统自动计算，并将两点间最短的路径连接起来，用明显颜色的线段标示出来，见图1.图1校园导航系统最短路径实现1运用迪杰斯特拉算法实现最短路径在本导航系统中最短路径的实现是基于迪杰斯特拉（Dijkstra）算法，该算法的基本思想：令G=(V，E)为一个带权有向图，把图中所有顶点的集合V分成两组，第一组为已求最短路径的顶点集合S

4、（初始状态时只有源点在s里面，以后每找到一条最短路径，就将其对应顶点加入集合S里面，直到全部顶点都加入到S里面）；第二组是未确定最短路径的顶点集合U.在向集合添加点的过程中，总是保持从源点v到S中各顶［2］点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度.图2是应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程，通过计算，源点到最后一个收稿日期：2014-02-24作者简介：杨伟龙（1971-），男，广东韶关人，韶关学院档案馆馆员，主要从事档案信息化管理方面的研究.第4期杨伟龙，等：校园导航系统最短

5、路径的实现·21·［3］顶点的路径为：1->4->3->5，所以源点到最后一个顶点的最短路径长度：60.2校园导航系统实现最短路径的方法2.1程序设计思想实现校园地图上任意两点间最短路径的寻找并向用户呈现出来，设计思路是关键.由于校园线路可直接抽象为无向图，对于无向图的最短路径寻找，普遍采用的是［4］迪杰斯特拉算法，其最短路径实现的步骤见图3.图2最短路径的计算2.2具体实现过程迪杰斯特拉算法的基本思想是通过计算一个节点到其他所有节点的距离，也就是以起始点为中心向外层层扩展，直到扩展到终点为止，经计算对比得出最短路径.因此

6、，首先是定义节点，罗列从起点到终点经过的所有节点个数.（1）节点数据结构类型#defineMAX_V30//最大顶点个数typedefstruct{char*vexs［MAX_V］;//顶点向量intarcs［MAX_V］［MAX_V］;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph;（2）创建导航图函数intCreateUDN(MGraph&G)函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的图3最短路径的实现步骤路径值用邻接矩阵进行存储.例：G.vexs［1］=“学术交流

7、中心”;作用：使1号定点命名为“学术交流中心”;G.arcs［1］［0］=G.arcs［0］［1］=550;作用：使1号节点到2号节点的路径赋值为550，因为是无向图，所以2号节点到1号节点的路径长度［5］也应赋值为550，其他节点间的长度计算以此类推.2.3后台数据编辑在整个系统中，后台部分可以对点和路线进行编辑，使得最短路径有效而准确.编辑点和路线是利用flash技术编写的编辑器进行设置的，见图4.图4校园地图上编辑点和路线的界面·22·韶关学院学报·自然科学2014年可以根据需要添加若干顶点，点击右上方的“开始加点”

8、按钮，然后在相应的位置左键点击一下，就会出现图5的红点，加点完成后点击结束.如果要删除不需要的顶点，可以左键点击一下该顶点，然后点击右上方的“删除顶点”按钮，该顶点与之相关的连线就会删除.在点的基础上可以进行路线的编辑.左键点击需要连线的顶点不放，拖动鼠标，便会看到的黑线（见图5）.黑线会跟随鼠标变化，