Tips：這個系統是學校《大資料應用開發語言》的大作業，本身想直接在網上copy一下，結果發現校園導航系統的c/java等版本很多很多，而python版本非常之少，于是只能自己寫一個簡單版本的了，包含三個模塊：查詢學校地圖模塊、查詢兩點最短路徑、查詢多路徑資訊，
文章目錄
- 前言
- 一、題目
- 二、需求分析
- 1.要求
- 2.運行環境
- 3.開發語言
- 三、概要設計
- 1.系統流程圖
- 2.函式流程圖
- 四、詳細設計
- 1.類的分析與設計
- 2.函式的分析與設計
- 五、具體代碼實作
- 運行結果
- 主界面
- 學校資訊
- 查詢景點
- 查詢最短路徑
前言
隨著社會經濟的發展，政府對教育建設的投資越來越大，眾多高校開始擴建工程，校園占地面積大，樓宇種類多，體現出國家對教育的重視程度逐年上升，科教興國戰略時首當其沖，面對越來越大的學校，“迷路”成為眾多高校新生不得面臨的話題，這便需要校園導航系統來解決師生如何查詢樓宇、如何快速到達目的地問題，
本系統采取基于Floyd演算法來完成查詢兩點最短路徑、查詢多路徑資訊等問題，
一、題目
功能描述:設計你的學校的校園景點,所含景點不少于10個.有景點名稱,代號,簡介等資訊; 為來訪客人提供圖中任意景點相關資訊的查詢.測驗資料:由讀者根據實際情況指定.
二、需求分析
1.要求
（1）用Python語言實作程式設計；
（2）進行相關資訊處理；
（3）畫出查詢模塊的流程圖；
（4）系統的各個功能模塊要求用函式的形式實作；
（5）界面友好（良好的人機互交），程式要有注釋，
2.運行環境
（1）MacOS Big Sur 11.6.2系統
（2）PyCharm CE 2021
3.開發語言
大資料開發語言（Python）
三、概要設計
1.系統流程圖
2.函式流程圖
四、詳細設計
1.類的分析與設計
定義一個Attractions類來實作輸入和存放景點編號、名稱，
class Attractions:
num = 0 #景點編號
name = '' #景點名稱
定義一個Campus類來存放校園無向圖的邊和節點，并給各結點定義名稱，
class Campus:
att = ["","南大門","行政樓","三號樓","四號樓","圖書館","西大門","7號樓","八號樓","九號樓","操場","體育館","大操場"] #景點
edges = [[INF] * M] * M #邊
Nodes_Num = 0
edges_Num = 0 #總結點數，總邊數
定義一個Passing類來存放路徑堆疊、路徑數、堆疊頂數
class passing():
pathStack = [[0]*M] ##路徑堆疊
top = 0
count = 0 #堆疊頂位置，路徑數
visited = [[False]*M] #判斷是否已經經過
定義一個DIS類來存放path路徑和distence目的地，
class DIS:
distence = [[0] * M] * M #距離向量
path = [[0] * M] * M
2.函式的分析與設計
定義函式getCampus（）來讀取本地map.txt地圖資訊，將讀出來的資料放在Nodes_Num陣列和edges二維陣列中，
def getCampus(g):
file = r'./map.txt'
with open(file) as f:
i = 0
for line in f:
if i == 0:
tmp1,tmp2 = line.split(',')
g.Nodes_Num = int(tmp1)
g.edges_Num = int(tmp2)
i = 1
else:
x, y, w = line.split(',')
g.edges[int(x)][int(y)] = g.edges[int(y)][int(x)] = int(w)
定義check函式來判斷輸入字符是否合規，如果輸入正確回傳True，錯誤回傳False，
def check(ch):
if ch < 0 or ch > 12:
print("\n您的輸入有誤，請輸入0~12之間的數字！")
return False
else:
return True
定義getinf（）函式來查詢想要了解的景點資訊
def getinf(g):
poi = int(input("請輸入您想了解到景點，0結束:"))
while poi != 0:
print("以下是該景點資訊：")
print(g.inf[poi])
poi = int(input("請輸入您想了解到景點，0結束:"))
定義Search函式來實作查詢景點功能
def Search(g):
number = 0
while True:
putMap()
print("請問您想查看哪個景點（請輸入景點編號,輸入0結束）:")
input(number)
# system("cls") #清空螢屏
if(check(number)):
if(number == 0):
break
else:
print("景點編號:{}".format(g.att[number].num))
print("景點名稱:{}".format(g.att[number]))
定義shrotPath最短路徑函式中用三個for回圈陳述句就能實作，
def shortPath(g,dis):
for i in range(1,g.Nodes_Num+1): #初始化距離向量矩陣與路徑向量矩陣
for j in range(1,g.Nodes_Num+1):
dis.distence[i][j] = g.edges[i][j]
if i != j and dis.distence[i][j] != INF:
dis.path[i][j] = i #表示如果i和j相鄰，i到j需要經過i
else:
dis.path[i][j] = -1 #否則用 -1代表當前兩點不可達
for k in range(1,g.Nodes_Num+1): #遞推求解每兩景點的最短路徑
for i in range(1,g.Nodes_Num+1):
for j in range(1,g.Nodes_Num+1):
if dis.distence[i][j] > (dis.distence[i][k] + dis.distence[k][j]): #如果發現引入k點可以使得路徑更短
dis.distence[i][j] = dis.distence[i][k] + dis.distence[k][j] #更新最短路徑長度
dis.path[i][j] = k
定義最佳路徑函式bestPath來實作最佳路徑功能
def bestPath(g,dis):
vNum = [0,0,0,0,0,0,0,0,0,0,0,0,0]
count = 1 #記錄用戶輸入的編號資訊
len = 0 #統計全程路徑總長
vNum[count] = int(input(" 請輸入你要游覽的景點的編號（輸入0結束輸入）："))
while vNum[count] != 0 and count <= 12:
if vNum[count] == 0:
break
count += 1
vNum[count] = int(input(" 請輸入你要游覽的景點的編號（輸入0結束輸入）："))
print(" 已為您挑選最佳訪問路徑：")
i = 1
while vNum[i] > 0 and vNum[i + 1] > 0 : #遍歷所有輸入的景點
print("{}->".format( g.att[vNum[i]]),end='') #輸出路徑上的起點
Floyd_Print(g,dis, vNum[i],vNum[i + 1]) #利用Floyd演算法得到這兩點之間的最短路徑
len += dis.distence[vNum[i]][vNum[i + 1]] #算出最短路長度
i += 1
print(g.att[vNum[count - 1]]) #輸出路徑上的終點
print(" 全程總長為：{}m".format(len))
用列印函式print_shortPath（）和Floyd_Path()通過遞回實作列印兩點間的最短路徑，并將結果顯示到控制臺上，
def Floyd_Print(g,dis,start,end):
#遞回基：如果兩點相鄰或者兩點不可達，結束遞回
if dis.path[start][end] == -1 or dis.path[start][end] == end or dis.path[start][end] == start:
return
else:
Floyd_Print(g,dis, start, dis.path[start][end]) #將中間點作為終點繼續列印路徑
print('{}->'.format(g.att[dis.path[start][end]]),end='') #列印中間景點名字
Floyd_Print(g, dis,dis.path[start][end], end) #將中間點作為起點繼續列印路徑
#輸出并列印兩點間的最短路徑
def print_shortPath(g,dis):
start = int(input(" 請輸入起點編號："))
end = int(input(" 請輸入終點編號："))
print(" {}到{}的最短距離是{}M".format(g.att[start],g.att[end],dis.distence[start][end]))
print(" 最佳游覽路線：",end='')
print('{}->'.format(g.att[start]),end='') #輸出路徑上的起點
Floyd_Print(g,dis,start, end) #輸出路徑上的中間點
print(g.att[end]) #輸出路徑上的終點
五、具體代碼實作
import os
M = 15 # 校園景點數量
INF = 0x3f3f3f3f
class Campus:
att = ["","北大門","行政樓","信工樓","教學主樓","圖書館","西大門","師院賓館","體育樓","北苑食堂","澡堂","宿舍區","大操場"] #景點
inf = [['']] * M
edges = [[INF] * M] * M #邊
Nodes_Num = 0
edges_Num = 0 #總結點數，總邊數
def putMap():
print(" ")
print(" 鹽城師范學院（通榆校區）校園導游圖 ")
print(" ")
print(" ")
print(" =================================================================================================== ")
print(" 2:行政樓 ----6:西大門 ")
print(" / \\ / | \\ ")
print(" / \\ / | \\ ")
print(" / ----- | | ----- 7:師院賓館------ ")
print(" / \\ | | | | | ")
print(" / 3:信工樓--- | --------- | | ")
print(" =================================================================================================== ")
print(" | | | | / | 9: 北苑食堂 ")
print(" | | | | / | \\ ")
print(" | / \\ | / | --10: 澡堂 ")
print(" 1:北大門 / -5:圖書館 | | ")
print(" \\ / | / | ")
print(" \\ / | / /------------11:體育館 ")
print(" =================================================================================================== ")
print(" 4: 教學主樓----------------- | / | ")
print(" | | / | ")
print(" | 8: 體育樓------- | ")
print(" | | | ")
print(" --------------------------------------------12:大操場------------- ")
print(" ")
print(" =================================================================================================== ")
def putMenu():
print("")
print(" * * ******** * * ******** ")
print(" * * * * * * * ")
print(" ******* ******* * * * * ")
print(" * * * * * * * ")
print(" * * ******** ******* ******* ******** ")
print(" ")
print(" ")
print(" = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =")
print(" = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =")
print(" = = = =")
print(" = = 歡迎使用鹽城師范學院（通榆校區）校園導航系統 = =")
print(" = = = =")
print(" = = 請選擇服務: = =")
print(" = = = =")
print(" = = 1.學校資訊 4.退出系統 = =")
print(" = = = =")
print(" = = 2.尋找兩景點之間的最短路徑 = =")
print(" = = = =")
print(" = = 3.尋找多景點之間所有路徑 = =")
print(" = = = =")
print(" = = = =")
print(" = = = =")
print(" = = = =")
print(" = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =")
print(" = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =")
print()
op = input(" 請根據你的需求選擇操作：")
return op
def getCampus(g):
file = r'./map.txt'
inff = r'./information.txt'
for i in range(1,g.Nodes_Num+1):
for j in range(1,g.Nodes_Num+1):
if i == j:
g.edges[i][j] = 0
with open(file) as f:
i = 0
for line in f:
if i == 0:
tmp1,tmp2 = line.split(',')
g.Nodes_Num = int(tmp1)
g.edges_Num = int(tmp2)
i = 1
else:
x, y, w = line.split(',')
g.edges[int(x)][int(y)] = g.edges[int(y)][int(x)] = int(w)
with open(inff) as f:
for line in f:
tmp1,tmp2 = line.split(' ')
poi = int(tmp1)
g.inf[poi] = tmp2
def getinf(g):
poi = int(input("請輸入您想了解到景點，0結束:"))
while poi != 0:
print("以下是該景點資訊：")
print(g.inf[poi])
poi = int(input("請輸入您想了解到景點，0結束:"))
def check(ch):
if ch < 0 or ch > 12:
print("\n您的輸入有誤，請輸入0~12之間的數字！")
return False
else:
return True
def Search(g):
number = 0
while True:
putMap()
print("請問您想查看哪個景點（請輸入景點編號,輸入0結束）:")
input(number)
# system("cls") #清空螢屏
if(check(number)):
if(number == 0):
break
else:
print("景點編號:{}".format(g.att[number].num))
print("景點名稱:{}".format(g.att[number]))
class passing():
pathStack = [[0]*M] ##路徑堆疊
top = 0
count = 0 #堆疊頂位置，路徑數
visited = [[False]*M] #判斷是否已經經過
# def DFS_AllPath(g,p,start,end):
# dis=0 #總距離
# p.pathStack[p.top] = start #將起點入堆疊
# p.top += 1
# p.visited[start] = 1 #表示該點已經訪問過
# for i in range(1,g.Nodes_Num+1): #遍歷與這個結點相鄰的結點
# if g.edges[start][i] > 0 and g.edges[start][i] != INF and p.visited[i] == False: #如果與i不是自己并且這個點有可達路徑并且未被訪問過
# if i == end: #如果已經到達目的地
# print(" 第{}條道路:".format(p.count)) #將該路徑輸出
# p.count+=1
# for j in range(p.top):
# print(g.att[p.pathStack[j]]) #輸出該景點
# if(j < p.top-1):
# dis = dis + g.edges[p.pathStack[j]][p.pathStack[j+1]]
#
# dis = dis + g.edges[p.pathStack[p.top-1]][end] #計算最后一個邊長1
# print(g.att[end])
# print(" 總長度為: {}m\n".format(len))
#
# else: #如果還未達到
# DFS_AllPath(g,i,end) #遞回遍歷
# p.top -= 1 #出堆疊
# p.visited[i]=0 #釋放該節點
#
#
# def print_AllPath(g,p):
# p.flag=0
# start = 0 #起點
# end = 0 #終點
# p.top = 0 #初始化堆疊頂
# p.count = 1 #初始化路徑條數
# flag = 1
# while True:
# start = int(input(("\n 請輸入起點編號:")))
# if(check(start)):
# flag = 1
# break
#
# flag=0 #flag重新置0
# while True:
# end = int(input(("\n 請輸入終點編號:")))
# if(check(end)):
# flag = 1
# break
# print("")
# DFS_AllPath(g,p,start,end)
# print("")
#Floyd演算法求兩景點間的一條最短的路徑
class DIS:
distence = [[0] * M] * M #距離向量
path = [[0] * M] * M
def shortPath(g,dis):
for i in range(1,g.Nodes_Num+1): #初始化距離向量矩陣與路徑向量矩陣
for j in range(1,g.Nodes_Num+1):
dis.distence[i][j] = g.edges[i][j]
if i != j and dis.distence[i][j] != INF:
dis.path[i][j] = i #表示如果i和j相鄰，i到j需要經過i
else:
dis.path[i][j] = -1 #否則用 -1代表當前兩點不可達
for k in range(1,g.Nodes_Num+1): #遞推求解每兩景點的最短路徑
for i in range(1,g.Nodes_Num+1):
for j in range(1,g.Nodes_Num+1):
if dis.distence[i][j] > (dis.distence[i][k] + dis.distence[k][j]): #如果發現引入k點可以使得路徑更短
dis.distence[i][j] = dis.distence[i][k] + dis.distence[k][j] #更新最短路徑長度
dis.path[i][j] = k # 更新最短路徑上的經結點
# 遞回實作列印兩點間的最短路徑(不包括起始點)
def Floyd_Print(g,dis,start,end):
#遞回基：如果兩點相鄰或者兩點不可達，結束遞回
if dis.path[start][end] == -1 or dis.path[start][end] == end or dis.path[start][end] == start:
return
else:
Floyd_Print(g,dis, start, dis.path[start][end]) #將中間點作為終點繼續列印路徑
print('{}->'.format(g.att[dis.path[start][end]]),end='') #列印中間景點名字
Floyd_Print(g, dis,dis.path[start][end], end) #將中間點作為起點繼續列印路徑
#輸出并列印兩點間的最短路徑
def print_shortPath(g,dis):
start = int(input(" 請輸入起點編號："))
end = int(input(" 請輸入終點編號："))
print(" {}到{}的最短距離是{}M".format(g.att[start],g.att[end],dis.distence[start][end]))
print(" 最佳游覽路線：",end='')
print('{}->'.format(g.att[start]),end='') #輸出路徑上的起點
Floyd_Print(g,dis,start, end) #輸出路徑上的中間點
print(g.att[end]) #輸出路徑上的終點
def bestPath(g,dis):
vNum = [0,0,0,0,0,0,0,0,0,0,0,0,0]
count = 1 #記錄用戶輸入的編號資訊
len = 0 #統計全程路徑總長
vNum[count] = int(input(" 請輸入你要游覽的景點的編號（輸入0結束輸入）："))
while vNum[count] != 0 and count <= 12:
if vNum[count] == 0:
break
count += 1
vNum[count] = int(input(" 請輸入你要游覽的景點的編號（輸入0結束輸入）："))
print(" 已為您挑選最佳訪問路徑：")
i = 1
while vNum[i] > 0 and vNum[i + 1] > 0 : #遍歷所有輸入的景點
print("{}->".format( g.att[vNum[i]]),end='') #輸出路徑上的起點
Floyd_Print(g,dis, vNum[i],vNum[i + 1]) #利用Floyd演算法得到這兩點之間的最短路徑
len += dis.distence[vNum[i]][vNum[i + 1]] #算出最短路長度
i += 1
print(g.att[vNum[count - 1]]) #輸出路徑上的終點
print(" 全程總長為：{}m".format(len))
if __name__ == '__main__':
g = Campus()
dis = DIS()
p = passing()
getCampus(g) #從檔案讀取資訊建立校園地圖
shortPath(g,dis) #通過Floyd求出distence表與path表
while True :
op = putMenu()
while op != '0': #列印主選單
if op == '1':
putMap()
getinf(g)
os.system("pause")
os.system('cls')
op = putMenu()
elif op == "2":
putMap()
print_shortPath(g,dis) #兩景點間最短路徑查詢
os.system("pause")
os.system('cls')
op = putMenu()
elif op == "3":
putMap()
bestPath(g,dis) #多景點間訪問最優路線查詢
os.system("pause")
os.system('cls')
op = putMenu()
elif op == '4':
print("感謝使用！")
exit()
else:
print(" 對不起！沒有該選項對應的操作.")
os.system("pause")
os.system('cls')
op = putMenu()
information.txt和map.txt檔案資料需要自己根據實際情況填寫，
information.txt//存放學校地點相關資訊
map.txt//存放學校地圖（點、邊等資料）
運行結果
主界面
學校資訊
查詢景點
查詢最短路徑
提示：這里對文章進行總結：
在圖論的學習中，將每個地點可以近似表示為網路中的一個節點，將位置、位置標號以及相鄰位置標號寫在矩陣的一行，利用稀疏矩陣進行資料的存取，節約存盤空間，從存盤空間讀取區域內各點資訊，根據每個點的鄰接點構建鄰接矩陣，如果兩個節點相鄰，則在鄰接矩陣中置1，反之置0;再利用公示求得距離，將該距離賦給鄰接矩陣中為 1 的值，就得到最短路徑演算法中的權值矩陣，
如有全部課程設計內容可私（包含、原始碼、答辯ppt、演示視頻、檔案），歡迎大家批評指正1
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423367.html
標籤：其他