最短路徑算法在校園導游系統中的應用

楊麗萍

摘 要： 用無向網表示學校的平面圖，設計了該平面圖的存儲結構，并應用最短路徑算法實現了查詢圖中各景點的相關信息，以及查詢圖中任意兩個景點間的最短路徑的功能；應用克魯斯卡爾算法構造該平面圖的最小生成樹，求出可以連通所有景點的最短路徑。該系統為新生熟悉校園環境提供了方便。

關鍵詞： 無向網； 存儲結構； 最短路徑； 最小生成樹； 鄰接矩陣

中圖分類號：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.