校园导航系统最短路径的实现

校园导航系统最短路径的实现

杨伟龙，李步德，谢俊鹏

（韶关学院档案馆，广东韶关512005）

随着高校的发展，校园面积不断扩大，为适应数字化校园建设的要求，各高校开发设计了校园导航系统.查询最短路径的实现是校园导航系统主要功能之一，阐述了基于Flash技术开发平台，运用迪杰斯特拉（Dijkstra）算法实现校园导航系统最短路径的功能.

高校；导航系统；最短路径；迪杰斯特拉算法

随着国内高校的发展，校园面积不断扩大.校园内教学楼、办公楼、学生公寓、运动场馆、商业网点、绿化景点等林林总总、错综复杂，即使在学校工作、生活几年的老师或学生也未必清楚了解，对于外来办事的人员更会带来诸多不便.许多高校专门设计了校园电子地图导航系统，为师生和校外人士办事办公提供便利.为适应数字化校园建设的要求，韶关学院也自主开发了一款校园导航系统，系统在用3ds max构建了本校电子地图的基础上，采用了Flash开发及Action Script 3.0语言，结合PHP+MySQL进行设计，实现了基于Flash技术平台的校园虚拟地图导航系统［1］.

最短路径的实现是校园导航系统主要功能之一，用户设定起点和终点，系统自动计算，并将两点间最短的路径连接起来，用明显颜色的线段标示出来，见图1.

图1 校园导航系统最短路径实现

1 运用迪杰斯特拉算法实现最短路径

在本导航系统中最短路径的实现是基于迪杰斯特拉（Dijkstra）算法，该算法的基本思想：令G=(V，E)为一个带权有向图，把图中所有顶点的集合V分成两组，第一组为已求最短路径的顶点集合S（初始状态时只有源点在s里面，以后每找到一条最短路径，就将其对应顶点加入集合S里面，直到全部顶点都加入到S里面）；第二组是未确定最短路径的顶点集合U.在向集合添加点的过程中，总是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度［2］.

图2是应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程，通过计算，源点到最后一个顶点的路径为：1->4->3->5，所以源点到最后一个顶点的最短路径长度：60［3］.

2 校园导航系统实现最短路径的方法

2.1程序设计思想

实现校园地图上任意两点间最短路径的寻找并向用户呈现出来，设计思路是关键.由于校园线路可直接抽象为无向图，对于无向图的最短路径寻找，普遍采用的是迪杰斯特拉算法［4］，其最短路径实现的步骤见图3.

图2 最短路径的计算

图3 最短路径的实现步骤

2.2具体实现过程

迪杰斯特拉算法的基本思想是通过计算一个节点到其他所有节点的距离，也就是以起始点为中心向外层层扩展，直到扩展到终点为止，经计算对比得出最短路径.因此，首先是定义节点，罗列从起点到终点经过的所有节点个数.

（1）节点数据结构类型

#define MAX_V 30//最大顶点个数

typedefstruct

{

char*vexs［MAX_V］;//顶点向量

intarcs［MAX_V］［MAX_V］;//邻接矩阵

intvexnum,arcnum;//图的当前顶点数和弧数

}MGraph;

（2）创建导航图函数

int CreateUDN(MGraph&G)

函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的路径值用邻接矩阵进行存储.例：

G.vexs［1］=“学术交流中心”;

作用：使1号定点命名为“学术交流中心”;

G.arcs［1］［0］=G.arcs［0］［1］=550;

作用：使1号节点到2号节点的路径赋值为550，因为是无向图，所以2号节点到1号节点的路径长度也应赋值为550，其他节点间的长度计算以此类推［5］.

2.3后台数据编辑

在整个系统中，后台部分可以对点和路线进行编辑，使得最短路径有效而准确.

编辑点和路线是利用flash技术编写的编辑器进行设置的，见图4.

图4 校园地图上编辑点和路线的界面

可以根据需要添加若干顶点，点击右上方的“开始加点”按钮，然后在相应的位置左键点击一下，就会出现图5的红点，加点完成后点击结束.如果要删除不需要的顶点，可以左键点击一下该顶点，然后点击右上方的“删除顶点”按钮，该顶点与之相关的连线就会删除.

在点的基础上可以进行路线的编辑.左键点击需要连线的顶点不放，拖动鼠标，便会看到的黑线（见图5）.黑线会跟随鼠标变化，当接近另一顶点时，黑线会自动吸附在上面，松开左键便可完成连线，不松开继续拖动就可以选择其他点连线.

图5 编辑点和线

保存编辑的内容，点击右上方的“保存编辑”按钮，然后点击页面最上方的“提交”按钮，将数据提交至服务器，从而完成对路线的编辑.

3 功能测试

在韶关学院校园导航系统中，选取的校园景点有：信工楼，理工楼、音乐楼、美术楼、行政楼、南区一号教学楼、科技楼、图书馆、道平广场、紫荆苑、学术交流中心等.先通过搜索功能找到起点的位置，也可直接点击作为起点的建筑，并点击“设为起点”，同理，找到终点位置，点击“设为终点”，见图6.

图6 设置起点和终点

继续点击“开始寻路”，通过系统最短路径计算，一条蓝色粗线将起点和终点连接起来，为使用者提供了到目的地的路线.图7是以信工楼为起点道平广场为终点的最短路径.

图7 起点与终点的连线

利用迪杰斯特拉算法结合Flash技术设计的校园导航系统最短路径模块，结构简单，容易实现，并且给后台管理提高了极大的便利.该功能的实现提高了校园导航系统的实用性.

［1］彼得斯.Flash ActionScript3.0动画高级教程［M］.苏金国，荆涛，译.北京:人民邮电出版社，2010.

［2］刘茂华，王岩，周海壮.D算法最短路径在数字校园中的应用研究［J］.测绘通报，2012(S1):624-625.

［3］聂萍.校园智能电子导航系统分析与设计［D］.昆明:云南大学，2012.

［4］王樱，徐雨明.校园道路网最短路径的分析与实现［J］.衡阳师范学院学报，2004，25(6):77-79.

［5］李元臣，李维群.基于Dijkstra算法的网络最短路径分析［J］.微计算机应用，2004，25(3):3-4.

On how to achieve the shortest path campus navigation system

YANG Wei-long,LI Bu-de,XIE Jun-peng
(Archives,Shaoguan University,Shaoguan 512005,Guangdong,China)

With the development of colleges and universities,campus area is expanding.To meet the requirements of digital campus construction,it is necessary to develop and design the university campus navigation system.Query shortest path to achieve campus navigation system is one of the main functions,and this paper describes the development platform based on Flash technology,and makes the use of Dijkstra algorithm to achieve the shortest path campus navigation system functions.

university；navigation system；shortestpath；Dijkstra algorithm

TP311.5

A

1007-5348（2014）04-0020-04

（责任编辑：欧恺）

2014-02-24

杨伟龙（1971-），男，广东韶关人，韶关学院档案馆馆员，主要从事档案信息化管理方面的研究.