最短路径算法在校园导游系统中的应用.pdf

《最短路径算法在校园导游系统中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机时代2014年第2期·31·最短路径算法在校园导游系统中的应用★杨丽萍(包头师范学院信息科学与技术学院，内蒙古包头0140301摘要：用无向网表示学校的平面图，设计了该平面图的存储结构，并应用最短路径算法实现了查询图中各景点的相关信息，以及查询图中任意两个景点间的最短路径的功能；应用克鲁斯卡尔算法构造该平面图的最小生成树，求出可以连通所有景点的最短路径。该系统为新生熟悉校园环境提供了方便。关键词：无向网；存储结构；最短路径；最小生成树；邻接矩阵中图分类号：TP312文献标志码：A文章编号：1006—8228(2014

2、)02—31—02ApplicationofshortestpathalgorithminthecampusguidesystemYangLiping(InformationScienceandTechnologyDepartment，BaotouNormalInstitute，Baotou，Neimenggu014030,China)Abstract：InthispapeLthemapofcampusisdrawnbyundirectedgraph，thestoragestructureofthemapisdesigne

3、d．Theshortestpathalgorithmisusedtoachievequeryingrelevantinformationofvariousviewspotsincampusandtheshortestpathbetweenanytwospots．Kruskalalgorithmisappliedtoobtaintheminimumspanningtreeoftheplanargraph，andfindtheshortestpathconnectingallview·spots．Thesefunctionsw

4、illprovideconveniencefornewstudentstogetfamiliarthecampusenvironment．Keywords：undirectedgraph；storagestructure；shortestpath；minimumspanningtree；adjacencymatrix0引言)VertexData；每年新生入学，来自全国各地的学生怀揣理想来到美丽的typedefstructArcNode{floatadj；，★两个景点之间路径的长度，校园，然而大学校园占地庞大，景点复杂，让很

5、多新生一开始都charinfo；／★两个景点之间路径的其他相关信息，很茫然，他们需要一个指导以便尽快熟悉学习和生活环境。因)ArcNode；此，本文应用最短路径算法和最小生成树算法设计了一个校园typedefstruct(导游系统，为新生提供方便。VertexDatavexs[MAX_VERTEX_NUM]；，★顶点向量／1校园景点平面图表示方法ArcNodearcs【MAX_VERTEX_NUM][MAX_VERTEX_NUM]；，★邻接矩阵／用无向网表示景点平面图，图中顶点表示主要景点，存储intvexnum，arcn

6、um；，★图的顶点数和弧数，景点的编号、名称、简介等信息，图中的边表示景点间的道路，}AdjMatrix；存储路径长度等信息。2最短路径算法描述存储结构的设计如下：设图g用邻接矩阵法表示，求图g中任意一对顶点Vi、vj间本文采用邻接矩阵表示法(AdjacencyMatrix)来实现图中的最短路径的算法如下。信息的存储，即采用两个数组来表示图：一个是用于存储顶点(一1)将vi到Vj的最短的路径长度初始化为g．arcs[i][j]．adj，信息的一维数组，另一个是用于存储图中顶点之间莱联关系然后进行如下n次比较和修正。的二维数

7、组，这个关联关系数组称为邻接矩阵。存储结构设(0)在vi、vj问加入顶点v0，比较(vi，vO，vj)和(vi，Vj)的路径计如下：#defineMAXVERTEXNUM10，★最多顶点个数，的长度，取其中较短的路径作为vi到vj的且中间顶点号不大__#defineINFINITY32768／★表示极大值即o。，于0的最短路径。typedefstructVertexData{(1)在Vi、vj间加入顶点vl，得(vi，⋯，v1)和(vl，⋯，vj)，其中charcode；素羔编号

8、(vi，⋯，v1)是vi到vl的且中间顶点

9、号不大于0的最短路径，charname；，★景点名称／(vl，⋯，Vj)是v1到vj的且中间顶点号不大于0的最短路径，这charinfo；，★景点简介，两条路径在上一步中已求出。将(vi，⋯，vl，⋯，vj)与上一步已求收稿日期：20131卜29基金项目：包头师范学院教改课题(BSJGI1024)作者简