基于Floyd算法的校园导航系统（Python版）

Tips：这个系统是学校《大数据应用开发语言》的大作业，本身想直接在网上copy一下，结果发现校园导航系统的c/java等版本很多很多，而python版本非常之少，于是只能自己写一个简单版本的了。包含三个模块：查询学校地图模块、查询两点最短路径、查询多路径信息。

文章目录

前言

随着社会经济的发展，政府对教育建设的投资越来越大。众多高校开始扩建工程，校园占地面积大，楼宇种类多。体现出国家对教育的重视程度逐年上升，科教兴国战略时首当其冲。面对越来越大的学校，“迷路”成为众多高校新生不得面临的话题，这便需要校园导航系统来解决师生如何查询楼宇、如何快速到达目的地问题。
本系统采取基于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类来实现输入和存放景点编号、名称。

classAttractions:
     num =0#景点编号
     name =''#景点名称

定义一个Campus类来存放校园无向图的边和节点，并给各结点定义名称。

classCampus:
    att =["","南大门","行政楼","三号楼","四号楼","图书馆","西大门","7号楼","八号楼","九号楼","操场","体育馆","大操场"]#景点
    edges =[[INF]* M]* M  #边
    Nodes_Num =0
    edges_Num =0#总结点数，总边数

定义一个Passing类来存放路径栈、路径数、栈顶数

classpassing():
    pathStack =[[0]*M]##路径栈
    top =0
    count =0#栈顶位置，路径数
    visited =[[False]*M]#判断是否已经经过

定义一个DIS类来存放path路径和distence目的地。

classDIS:
    distence =[[0]* M]* M                                                   #距离向量
    path =[[0]* M]* M

2.函数的分析与设计

定义函数getCampus（）来读取本地map.txt地图信息，将读出来的数据放在Nodes_Num数组和edges二维数组中。

defgetCampus(g):file=r'./map.txt'withopen(file)as f:
        i =0for line in f:if i ==0:
                tmp1,tmp2 = line.split(',')
                g.Nodes_Num =int(tmp1)
                g.edges_Num =int(tmp2)
                i =1else:
                x, y, w = line.split(',')
                g.edges[int(x)][int(y)]= g.edges[int(y)][int(x)]=int(w)

定义check函数来判断输入字符是否合规，如果输入正确返回True，错误返回False。

defcheck(ch):if ch <0or ch >12:print("\n您的输入有误，请输入0~12之间的数字！")returnFalseelse:returnTrue

定义getinf（）函数来查询想要了解的景点信息

defgetinf(g):
    poi =int(input("请输入您想了解到景点，0结束:"))while poi !=0:print("以下是该景点信息：")print(g.inf[poi])
        poi =int(input("请输入您想了解到景点，0结束:"))

定义Search函数来实现查询景点功能

defSearch(g):
    number =0whileTrue:
        putMap()print("请问您想查看哪个景点（请输入景点编号,输入0结束）:")input(number)# system("cls") #清空屏幕if(check(number)):if(number ==0):breakelse:print("景点编号:{}".format(g.att[number].num))print("景点名称:{}".format(g.att[number]))

定义shrotPath最短路径函数中用三个for循环语句就能实现。

defshortPath(g,dis):for i inrange(1,g.Nodes_Num+1):#初始化距离向量矩阵与路径向量矩阵for j inrange(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需要经过ielse:
                dis.path[i][j]=-1#否则用 -1代表当前两点不可达for k inrange(1,g.Nodes_Num+1):#递推求解每两景点的最短路径for i inrange(1,g.Nodes_Num+1):for j inrange(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来实现最佳路径功能

defbestPath(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]!=0and count <=12:if vNum[count]==0:break
        count +=1
        vNum[count]=int(input("             请输入你要游览的景点的编号（输入0结束输入）："))print("             已为您挑选最佳访问路径：")
    i =1while vNum[i]>0and 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 +=1print(g.att[vNum[count -1]])#输出路径上的终点print("             全程总长为：{}m".format(len))

用打印函数print_shortPath（）和Floyd_Path()通过递归实现打印两点间的最短路径，并将结果显示到控制台上。

defFloyd_Print(g,dis,start,end):#递归基：如果两点相邻或者两点不可达，结束递归if dis.path[start][end]==-1or dis.path[start][end]== end or dis.path[start][end]== start:returnelse:
        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)#将中间点作为起点继续打印路径#输出并打印两点间的最短路径defprint_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 =0x3f3f3f3fclassCampus:
    att =["","北大门","行政楼","信工楼","教学主楼","图书馆","西大门","师院宾馆","体育楼","北苑食堂","澡堂","宿舍区","大操场"]#景点
    inf =[['']]* M
    edges =[[INF]* M]* M  #边
    Nodes_Num =0
    edges_Num =0#总结点数，总边数defputMap():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("        ===================================================================================================      ")defputMenu():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

defgetCampus(g):file=r'./map.txt'
    inff =r'./information.txt'for i inrange(1,g.Nodes_Num+1):for j inrange(1,g.Nodes_Num+1):if i == j:
                g.edges[i][j]=0withopen(file)as f:
        i =0for line in f:if i ==0:
                tmp1,tmp2 = line.split(',')
                g.Nodes_Num =int(tmp1)
                g.edges_Num =int(tmp2)
                i =1else:
                x, y, w = line.split(',')
                g.edges[int(x)][int(y)]= g.edges[int(y)][int(x)]=int(w)withopen(inff)as f:for line in f:
            tmp1,tmp2 = line.split(' ')
            poi =int(tmp1)
            g.inf[poi]= tmp2
defgetinf(g):
    poi =int(input("请输入您想了解到景点，0结束:"))while poi !=0:print("以下是该景点信息：")print(g.inf[poi])
        poi =int(input("请输入您想了解到景点，0结束:"))defcheck(ch):if ch <0or ch >12:print("\n您的输入有误，请输入0~12之间的数字！")returnFalseelse:returnTruedefSearch(g):
    number =0whileTrue:
        putMap()print("请问您想查看哪个景点（请输入景点编号,输入0结束）:")input(number)# system("cls") #清空屏幕if(check(number)):if(number ==0):breakelse:print("景点编号:{}".format(g.att[number].num))print("景点名称:{}".format(g.att[number]))classpassing():
    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算法求两景点间的一条最短的路径classDIS:
    distence =[[0]* M]* M                                                   #距离向量
    path =[[0]* M]* M

defshortPath(g,dis):for i inrange(1,g.Nodes_Num+1):#初始化距离向量矩阵与路径向量矩阵for j inrange(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需要经过ielse:
                dis.path[i][j]=-1#否则用 -1代表当前两点不可达for k inrange(1,g.Nodes_Num+1):#递推求解每两景点的最短路径for i inrange(1,g.Nodes_Num+1):for j inrange(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                               # 更新最短路径上的经结点# 递归实现打印两点间的最短路径(不包括起始点)defFloyd_Print(g,dis,start,end):#递归基：如果两点相邻或者两点不可达，结束递归if dis.path[start][end]==-1or dis.path[start][end]== end or dis.path[start][end]== start:returnelse:
        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)#将中间点作为起点继续打印路径#输出并打印两点间的最短路径defprint_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])#输出路径上的终点defbestPath(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]!=0and count <=12:if vNum[count]==0:break
        count +=1
        vNum[count]=int(input("             请输入你要游览的景点的编号（输入0结束输入）："))print("             已为您挑选最佳访问路径：")
    i =1while vNum[i]>0and 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 +=1print(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表whileTrue:
        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