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

杨丽萍

摘 要： 用无向网表示学校的平面图，设计了该平面图的存储结构，并应用最短路径算法实现了查询图中各景点的相关信息，以及查询图中任意两个景点间的最短路径的功能；应用克鲁斯卡尔算法构造该平面图的最小生成树，求出可以连通所有景点的最短路径。该系统为新生熟悉校园环境提供了方便。

关键词： 无向网； 存储结构； 最短路径； 最小生成树； 邻接矩阵

中图分类号：TP312 文献标志码：A 文章编号：1006-8228（2014）02-31-02

0 引言

每年新生入学，来自全国各地的学生怀揣理想来到美丽的校园，然而大学校园占地庞大，景点复杂，让很多新生一开始都很茫然，他们需要一个指导以便尽快熟悉学习和生活环境。因此，本文应用最短路径算法和最小生成树算法设计了一个校园导游系统，为新生提供方便。

1 校园景点平面图表示方法

5 测试与分析

5.1 构造测试数据

6 结束语

本文将最短路径算法和克鲁斯卡尔算法应用于校园导游系统中，实现了查询任意两个景点间的最短路径和找出可以连通所有景点的最短路径，为新生熟悉校园环境提供了方便。

参考文献：

[1] 耿国华.数据结构—C语言描述[M].高等教育出版社，2005.

[2] 左孝凌等编.离散数学[M].上海科技文献出版社，1982.

[3] 谭浩强，张基温.C语言程序设计教程[M].高等教育出版社，2006.

[4] 何钦铭，颜晖.C语言程序设计[M].高等教育出版社，2008.