基于Floyd算法的校园导航系统（Python版） |
您所在的位置：网站首页 › 校园导游系统流程图 › 基于Floyd算法的校园导航系统（Python版） |
基于Floyd算法的校园导航系统（Python版）
|
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.系统流程图
定义一个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 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 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 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 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 |
【本文地址】
今日新闻 |
推荐新闻 |