简介数据结构课程期末项目“基于Python的zzu校园导航”完整实现包面向高校计算机专业学生、课程设计团队及图算法初学者。项目以郑州大学校园为实际场景综合运用DFS/BFS图遍历与Dijkstra、Bellman-Ford最短路径算法完成路径计算基于Tkinter构建交互界面并覆盖地图数据存储、坐标映射与异常处理模块适合作为课程设计参考或算法综合练习素材。压缩包共131个文件整体约7.13MB120张png截图展示各场景界面与运行效果5个Python源码文件为核心实现另有3个pyc编译文件、1份PDF介绍文档、1个中文字体文件及1个附加zip包目录清晰便于按模块学习。已有69人学习下载。资料内含算法思路导图、多场景导航运行截图与完整代码读者既可借此理解图算法从理论到落地的完整链路也可参考界面设计、测试用例与异常处理方式拓展至其他校园或园区导航项目。1. 为什么数据结构期末作业我会选“校园导航”一个好讲清楚图的题目数据结构课期末作业最怕的不是算法难而是题目太虚——写一个图书管理系统全班三十份作业长一个样写一个迷宫求解评审看两分钟就腻。我当年选的是“基于 Python 的 zzu 校园导航”核心原因是它天然对应图论里的最短路径能同时把图的存储结构、遍历方式、Dijkstra 算法和工程封装都摊开讲明白而且演示效果直观在界面里点两个建筑物路径立刻画出来比输出一串数字有说服力得多。这篇笔记就是我当时跑通的完整实现思路从图建模到 GUI 到交作业前的验收适合正被数据结构作业卡住、想选导航类题目又怕做不完的人。你不需要懂复杂的 GIS 知识Python 会写类、会用字典和列表就能跟着复现。2. 把地图变成图zzu 校园导航的数据结构选型与建模2.1 为什么“校园导航”本质上是一个图问题而不是数组问题校园导航要解决的业务问题是给定两个地点比如“图书馆”和“行政楼”找到一条经过的道路总长度最短的路线。这背后有一个很经典的形式化过程——把每个建筑物抽象成顶点Vertex把建筑物之间实际存在的道路抽象成边Edge把道路的长度米作为边的权值Weight于是整个校园就变成了一张带权无向图Weighted Undirected Graph。选这个模型的理由要能在答辩时说出来数据结构课中学的线性表、栈、队列本质都是“一对一”或“一对多”的关系而地图上任意两个地点之间都可能连通这是一种“多对多”的关系只能由图来刻画。图这个结构不是为导航发明的但它恰好能把导航的物理世界映射成程序能处理的数据。这个映射过程有一个专门的说法叫“图建模”Graph Modeling作业评审关心的第一件事往往就是你有没有把真实世界抽象成图的这一步而不是你有没有把 Dijkstra 代码背下来。2.2 邻接表还是邻接矩阵这份作业怎么选依据是什么图的存储方式在数据结构课本里主要有两种邻接矩阵Adjacency Matrix和邻接表Adjacency List。做这个题之前必须先想清楚用哪个因为后面所有算法都建立在存储结构之上。邻接矩阵用二维数组存matrix[i][j]表示顶点 i 到顶点 j 的边的权值连通为具体路程不连通为无穷大。它的优点是判断两个顶点是否相邻是 O(1) 时间缺点是空间复杂度固定为 O(V²)V 是顶点数。校园导航的顶点规模一般在 20 到 50 个之间矩阵也就几百个元素空间完全不是问题。邻接表则用“数组 链表”或“字典 列表”实现每个顶点后面挂一个链表存它能到达的邻居和对应权值。优点是稀疏图下省空间遍历某个顶点的所有邻居时效率高缺点是代码结构稍微复杂一点而且判断两个顶点是否相邻需要遍历链表。我的建议是选邻接表但用 Python 的字典来实现。为什么因为这是期末作业不是工程系统你需要向评审展示“我懂邻接表的原理”而 Python 字典天然就是“顶点 - 邻居列表”的映射代码可读性极高答辩时一句话能讲清楚。更重要的是Dijkstra 算法在邻接表上的实现比邻接矩阵更自然——你只需要遍历当前顶点的邻居不需要扫描一整行矩阵这能让你的算法复杂度分析站得住脚后面会细说。2.3 从零写地图数据把 zzu 的楼和路存成字典建模的第一步是收集数据。我当时是在校园地图上人工数出了 15 个主要节点南门、北门、图书馆、教学楼 A/B/C 栋、行政楼、食堂一/二、体育馆、宿舍区、实验楼、校医院、计算机学院楼等。然后目测或根据校园地图比例尺估算每两个相邻节点间的步行距离米不相邻的节点之间不建边这样得到一张稀疏图。关键设计决策不要试图把任意两个楼都连起来那样图就稠密到失去意义了。真实校园里你从图书馆去食堂一定经过某个路口或某条主路这些中间点也必须建模成顶点。换句话说导航图中的顶点不只是目的地还包括路口、岔路。我当时在主干道上加了 3 个“虚拟路口点”让路径更贴近真实情况代码上完全没增加难度但演示效果和真实感会好很多。# graph.py # 图的邻接表存储字典的 key 是顶点名value 是 (邻居, 距离) 的列表 # 这是手工维护的静态地图数据真实项目可以改用 JSON 或数据库但作业用常量文件就够了 MAP_DATA { 南门: [(行政楼, 180), (实验楼, 240)], 行政楼: [(南门, 180), (图书馆, 120), (教学楼A, 90)], 图书馆: [(行政楼, 120), (教学楼B, 150), (食堂一, 100)], 教学楼A: [(行政楼, 90), (教学楼B, 110), (计算机学院楼, 200)], 教学楼B: [(图书馆, 150), (教学楼A, 110), (教学楼C, 80)], 教学楼C: [(教学楼B, 80), (实验楼, 160), (食堂二, 130)], 实验楼: [(南门, 240), (教学楼C, 160), (校医院, 100)], 计算机学院楼: [(教学楼A, 200), (体育馆, 120)], 体育馆: [(计算机学院楼, 120), (宿舍区, 240)], 宿舍区: [(体育馆, 240), (食堂二, 180), (北门, 260)], 食堂一: [(图书馆, 100), (食堂二, 140)], 食堂二: [(教学楼C, 130), (宿舍区, 180), (食堂一, 140)], 校医院: [(实验楼, 100), (北门, 320)], 北门: [(宿舍区, 260), (校医院, 320)], }这段代码的逻辑说明整个图就是一个个元组组成的列表每个元组是“去往哪个顶点、路程多少米”。注意我把主干道的“路口”也建模成了顶点比如“教学楼B”连接行政楼、图书馆、教学楼A、教学楼C天然承担了路口职能这是导航图建模里非常常见的手法——中间节点不仅给人指路还把图切出层次。参数说明距离单位统一为米不建议混用公里边的权值必须是正数因为 Dijkstra 算法要求非负权如果后期要加“通行时间”作为权值只需要把这个数字换成时间秒数其余逻辑完全不变。自测方法随便选一个顶点数一下它的邻居数量和 MAP_DATA 里对应列表长度一致即可。更严谨一点可以写一个函数验证图的连通性从南门出发遍历所有顶点确保没有孤立节点——这个坑我在避坑章节还会提。3. 导航核心算法Dijkstra 最短路径的实现细节与参数调校3.1 Dijkstra 为什么是这道题的“标准答案”以及它的局限在哪里数据结构课程里讲最短路标准解法就是 Dijkstra 算法。它的核心思想是贪心维护一个“已确定最短距离的顶点集合”S 和一个“未确定顶点到源点的当前最短距离”数组 dist每次从 S 外取出 dist 值最小的顶点 u用 u 去松弛Relax它的所有邻居。所谓松弛就是检查“经过 u 到邻居 v 是否比之前记录的 dist[v] 更短”如果更短就更新。选 Dijkstra 而不选 Floyd 的原因是Floyd 一次算出所有点对之间的最短路代码确实更短三层循环但它的时间复杂度是 O(V³)而且答辩时很难解释“为什么你要算全校任意两点之间的最短路而程序里只需要一对一的导航”。Dijkstra 的单源最短路特性正好匹配导航场景你选一个起点只需要得到这一个源点到所有点的最短路然后取出目标点的那条。Dijkstra 有一个学校教材里不常强调、但实验中一定会碰到的条件图中不能有负权边。负权会破坏贪心选择的正确性因为一旦出现负数之前被判定为“已最短”的路径可能因为一条负权边反而变长。校园导航里的距离都是正数所以安全如果你的期末作业想扩展成“带红绿灯等待时间的导航”这里的等待时间也是非负的依然安全。如果哪天你做一个带“下坡捷径 -5 米”这种诡异数据的图那就得换 Bellman-Ford但这不是本作业范围。3.2 用 Python 手写 Dijkstra最小堆版与代码注释课本上的 Dijkstra 伪代码用数组找最小值复杂度 O(V²)。Python 里更常规的写法是用优先队列heapq 最小堆来维护“当前距离最小的未确定顶点”复杂度能降到 O((VE)logV)E 是边数。这道题的顶点只有十几个V² 完全够用但用堆实现的代码更能体现你对 Python 数据结构的理解——heapq 本身就是一个数据结构知识点答辩时可以顺带讲。# dijkstra.py import heapq def dijkstra(graph, source, target): 基于最小堆的 Dijkstra 最短路算法 :param graph: 邻接表格式同 MAP_DATA :param source: 起点顶点名 :param target: 终点顶点名 :return: (距离, 路径顶点列表)若不存在路径返回 (float(inf), []) # 初始化距离表所有顶点距离为无穷大源点距离为 0 dist {vertex: float(inf) for vertex in graph} prev {vertex: None for vertex in graph} # 记录每个顶点的前驱用于回溯路径 dist[source] 0 # 最小堆里存 (当前距离, 顶点名) heap [(0, source)] while heap: current_dist, current heapq.heappop(heap) # 如果弹出的是某个顶点的过期记录距离不是最新的直接跳过 if current_dist dist[current]: continue # 提前终止当前已经是目标顶点说明最短路已经确定 if current target: break # 松弛当前顶点的所有邻居 for neighbor, weight in graph[current]: new_dist current_dist weight if new_dist dist[neighbor]: dist[neighbor] new_dist prev[neighbor] current heapq.heappush(heap, (new_dist, neighbor)) # 这里不能直接 return因为堆里可能有其他顶点距离更小 # 回溯路径 path [] node target while node is not None: path.append(node) node prev[node] path.reverse() if dist[target] float(inf): return float(inf), [] return dist[target], path这段代码有三个容易被忽略的参数细节我逐一说明。第一个是堆中存储的格式(current_dist, current)Python 的元组比较会先比较第一个元素所以堆会自动按距离排序第二个是“过期记录跳过”的判断if current_dist dist[current]因为同一个顶点可能被加入堆多次老记录在堆底弹出时距离已经比 dist 里的最新值大不跳过会重复松弛虽然结果不错但性能差且逻辑不干净第三个是松弛时的严格不等号new_dist dist[neighbor]这里必须用严格小于如果改成遇到等权路径时 prev 可能被反复更新路径回溯会不稳定——这在作业里不致命但答辩时被问到了会显得基础不牢。3.3 从 dist 数组到完整路径回溯 prev 时最容易写错的一种情况调用上面这个函数时很多人会以为返回的就直接是一条从 source 到 target 的路径测试却发现路径只有两个端点中间楼全丢了。原因出在回溯的终止条件上。我第一次写的时候用的是while node ! source看起来没毛病但如果你给的 target 就是 source起点即终点循环体一次都不执行path 里只有一个 target然后你手动把 path 反转成[target]再往里加 source 就变成[source, target]顺序反了且没有中间节点。正确做法是像上面代码那样prev[source]保持为 None回溯统一用while node is not None作为终止条件。这相当于给回溯画了一条从 target 一路指回 source 的链表None 就是链表的结尾哨兵。如果你坚持要写while node ! source就必须额外处理“起点等于终点”这个分支否则输出结果会是一个空路径或错误路径。我给这段代码加了一个if dist[target] float(inf)的判断处理不连通的情况——虽然我的 MAP_DATA 完全连通但你不保证你自己的数据不出意外保留这个判断是交作业前最省事的自保手段。另一个和路径相关的坑是距离表的初始化float(inf)是 Python 表示正无穷的标准写法不要用一个大整数比如9999999代替。用大整数虽然能跑通但在松弛比较时可能出现“恰好路径总长超过 9999999”这种薛定谔的 bug用 inf 后任何有限数都比它小逻辑上不会出错。至于 prev 的初始值设为 None是为了配合回溯链表的终止判断逻辑上和 source 的 prev 永远是 None 是一致的。4. 让导航看得见用 Tkinter 搭一个能点的校园地图界面4.1 图形界面选 Tkinter 还是 Pygame一份期末作业该怎么取舍导航算法跑通之后只是命令行输出演示效果大打折扣。我当时先试了 Pygame发现它适合做游戏画点、画线、响应鼠标事件都要自己管而且刷新机制是游戏帧循环跟“点击一下出结果”这种交互模式其实不太匹配。后来换成了 Python 自带的 Tkinter理由很朴素它不需要额外安装第三方库任何机器上有 Python 就能跑评审打开你的源码不需要 pip install 任何依赖这对期末作业来说是最重要的优势。Tkinter 的绘图模型是 Canvas画布可以在上面画直线、圆形、文字。这对导航界面够用了建筑物画成带名字的节点圆道路画成连线最短路径高亮画成红色粗线。它的劣势是 UI 样式比较老旧没有现代网页那种圆角和渐变色但作业评审更看重你能否清晰展示数据结构和算法流程不需要精美到产品级。4.2 画底图、布坐标、绑定点击事件一个最小可跑 GUI 骨架Tkinter 里最关键的是“坐标系统”。你需要给每个顶点分配一个 (x, y) 像素坐标然后在地图画布上把这些点连成道路。我的做法是新建一个字典POSITIONS {南门: (100, 600), 行政楼: (150, 480), ...}像素坐标是我对着校园地图按比例缩放的不是精确的经纬度但在作业演示层面形似和路线合理就够用了。# gui.py import tkinter as tk from tkinter import messagebox from graph import MAP_DATA from dijkstra import dijkstra # 每个顶点的画布像素坐标(x, y) POSITIONS { 南门: (100, 600), 行政楼: (150, 480), 图书馆: (250, 360), 教学楼A: (220, 400), 教学楼B: (330, 300), 教学楼C: (420, 260), 实验楼: (380, 420), 计算机学院楼: (300, 220), 体育馆: (450, 120), 宿舍区: (600, 150), 食堂一: (330, 420), 食堂二: (520, 280), 校医院: (500, 480), 北门: (650, 350), } class CampusNavApp: def __init__(self, root): self.root root self.root.title(zzu 校园导航数据结构期末作业) self.canvas tk.Canvas(root, width750, height650, bgwhite) self.canvas.pack(sidetk.LEFT) self.info tk.Label(root, text点击起点再点击终点, font(SimHei, 14)) self.info.pack(sidetk.TOP, filltk.X) self.start None # 正在等待终点时的起点 self._draw_map() # 先画静态底图节点 道路 def _draw_map(self): # 先画所有边道路再画节点保证节点圆盖在线上这样圆里不会被线覆盖 for u in MAP_DATA: x1, y1 POSITIONS[u] for v, _ in MAP_DATA[u]: x2, y2 POSITIONS[v] self.canvas.create_line(x1, y1, x2, y2, fillgray, width2) for name, (x, y) in POSITIONS.items(): self.canvas.create_oval(x - 15, y - 15, x 15, y 15, filllightblue, outlineblack, width2) self.canvas.create_text(x, y, textname, font(SimHei, 10))上面这段代码只实现了静态地图绘制还差点击事件。要点是create_line和create_oval的绘制顺序会互相覆盖先把所有边画完再画节点节点的浅蓝色圆能把道路线遮住视觉上“道路从建筑旁边穿过”而不是“建筑盖在道路十字交叉的正上方”。比例尺参数在 POSITIONS 里调如果你加了新顶点记得在该字典里补齐坐标否则画布会直接报 KeyError。4.3 从“能跑”到“像样”路线高亮与信息面板点击交互的逻辑是第一次点击记录起点第二次点击记录终点并调用 dijkstra把返回路径上的线段改成红色粗线。注意这里有个隐藏问题——Canvas 绘制过的对象不能改颜色要在创建时保存对象的 ID。所以在画静态地图时我需要给每一条道路的create_line返回值存进字典self.edge_ids {(u, v): line_id}路线高亮时找到对应 ID调用itemconfig(line_id, fillred, width4)就能变色。def _on_click(self, event): # 绑定到 canvas 的 Button-1 事件 # 根据点击像素坐标命中最近的顶点 best_name None best_d float(inf) for name, (x, y) in POSITIONS.items(): d (event.x - x) ** 2 (event.y - y) ** 2 if d best_d and d 30 * 30: # 最多偏离节点 30 像素才算命中 best_d d best_name name if best_name is None: self.info.config(text没点中建筑再试一次) return if self.start is None: self.start best_name self.info.config(textf起点{best_name}再点终点) else: end best_name dist, path dijkstra(MAP_DATA, self.start, end) self.show_path(self.start, end, dist, path) self.start None这段代码里“像素命中”用的是欧氏距离平方比较而不是开方因为比较大小不需要真正开根省掉math.sqrt的开销这是一种常见的计算优化习惯虽然这里数据量小体现不出来但在答辩时说出这个理由能体现你对计算细节的敏感。30 像素是命中半径参数我按 750x650 的画布大小调的太大会出现“点了空白处却选中了远处建筑”的误触太小则要精准点击圆中心演示时容易出丑。事件绑定的唯一注意点是 Canvas 上要先设置canvas.bind(Button-1, self._on_click)而且是在创建画布后立刻绑定绑定晚了你点第一次事件永远不会触发。5. 避坑手册zzu 导航作业里最常见的 5 个翻车现场5.1 翻车现场一导入模块就报 ModuleNotFoundError根因是相对路径和运行方式现象在 IDE 里直接右键运行gui.py报错ModuleNotFoundError: No module named dijkstra。或者同学把 zip 解压后双击运行同样报错。原因大多数同学在写作业源码时喜欢把所有文件平铺在同一个文件夹用 IDE 运行时当前工作目录不一定是源码所在目录Python 会把“当前目录”加入模块搜索路径而不是“源码文件所在目录”。平铺文件在 PyCharm 里跑没问题但换个环境或者从 zip 解压后双击运行工作目录变了就找不到模块。解决两个办法任选其一。一是在gui.py顶部加上import sys, os sys.path.append(os.path.dirname(os.path.abspath(__file__)))二是不用模块导入把所有代码合并进一个文件文件名随便但这样做会牺牲模块化。我建议用第一种因为模块拆分本身是数据结构作业的加分项——你可以在答辩时说“我把图的数据、算法、界面分成三个模块分别负责数据层、逻辑层、表现层”。5.2 翻车现场二Dijkstra 输出路径总是缺楼回溯 prev 的初始值设错了现象从“南门”到“教学楼B”程序输出[南门, 教学楼B]但图里明明有“行政楼”这个中间点。原因prev列表的初始化用了{}回溯时从 target 出发一路node prev[node]到 source 时 prev[source] 的值是 None循环停住导致路径丢失了中间的“行政楼”。如果你把 prev 初始化成每个节点的“前驱是它自己”回溯时遇到 source 就 break但 source 自己也被当成了两个节点路径会变成[南门, 行政楼, 南门, 教学楼B]这种重复。解决把 prev 的默认值统一设为 Nonesource 的 prev 保持 None。回溯循环以while node is not None判断反转后正好是从 source 到 target 的完整路径。写完后跑一个“起点到起点”的自测从南门到南门应当输出[南门]和距离 0如果输出空列表或抛 KeyError就是这条边界没处理。5.3 翻车现场三点击地图上的建筑路线画出来却穿墙而过现象在 GUI 界面里点“图书馆”到“体育馆”画出来的高亮道路直接穿过另一个建筑物圆点视觉效果很假。评审看了会质疑你的地图数据不真实。原因这不是算法错误而是“图的结构”和“画的布局”不一致。我在 MAP_DATA 里给“教学楼B”定义了三条边分别通向图书馆、教学楼A、教学楼C但我在界面布局时把教学楼B放在了三个邻居的几何中心附近三条线必然穿过它的圆。真实地图里道路不会穿过建筑物但因为布局是手调的就可能出现这种伪交叉。解决调整布局或调整边。最简单的办法是调整 POSITIONS 坐标让道路绕开节点圆更规范的做法是把真实地图扫描后按坐标描点而不是手动摆位置。我当时折中处理把教学楼B移到画布偏右下让三条边变成类似三角形的三条边穿过感大幅减弱。检查方法逐条遍历所有边检查线段与节点圆心之间的距离是否小于节点半径15 像素如果小于就输出警告。这种自检代码写几行就能做但很少有人做属于典型的“验收前不看整体图”的失误。5.4 翻车现场四zip 包发过去评审解压后运行直接闪退现象源码在自己电脑跑得好好的交压缩包后对方一运行窗口一闪而过根本看不到界面或直接报TclError: no display之类的错。原因有两种典型情况。第一种是你运行时没加root.mainloop()或者你的代码里把mainloop写到了某个函数内部而不是最外层导致窗口创建后立即销毁。第二种是压缩包里包含了你本机的绝对路径比如你导入了位于D:/myproject/campus_nav下的资源文件而评审解压到了桌面路径失效。解决交作业前用“解压后换个目录运行”的方式自测至少一遍。具体操作把原文件夹复制到一个完全不相干的路径比如C:/tmp/下解压 zip然后运行。如果窗口能正常弹出说明路径适配没问题。还有一个很容易被忽略的点Tkinter窗口里控件字体如果你指定了font(SimHei, 14)当评审机器没有中文字体时控件会显示方框。保险做法是在代码里做一次字体探测找不到宋体就回退到默认字体import tkinter.font as tkfont try: tkfont.Font(familySimHei) except tk.TclError: info_font (Arial, 14) # 回退字体5.5 翻车现场五算法跑得慢界面一卡一卡原因是你把搜索放在了主线程现象点完终点之后界面卡住几十毫秒到几秒不等像死机一样然后突然出结果。顶点多的时候更明显。原因Tkinter 的mainloop是单线程事件循环你的 Dijkstra 计算如果直接在鼠标事件回调里执行会阻塞事件循环期间界面无法重绘、无法响应鼠标直到算法返回。虽然你的图只有十几个顶点Dijkstra 运行时间在毫秒级但卡片现象依然存在因为中间还有路径高亮的重绘操作。解决这个图规模完全不需要开线程最简单的优化是不做耗时操作。你只需要在点击终点后先更新状态文本为“计算中…”然后立刻调用self.root.update()强制刷新一次画面再执行算法最后画路径。update()是 Tkinter 里非常实用的一个低频 API它能让事件循环在长任务期间依然处理部分重绘请求。如果哪天真要扩展到全校几百个楼那就改用threading.Thread开一个后台线程执行 Dijkstra界面线程只负责接收结果画线。期末作业能用update()解决就够用了开线程反而要处理线程安全复杂度陡增。6. 交作业前做一轮自验收检查连通性、边界路径和演示话术验收的第一步写一个命令行自测脚本脱离界面直接验证算法正确性。做法是遍历所有顶点对分别调用 dijkstra把每一对的路径打印出来肉眼扫一遍有没有“断头路”或“绕远路”。这里有一个很容易忽略的边界情况——图不是强连通图比如从“北门”到“南门”可能要走很远但只要路径存在就不算错真正的问题是有孤立顶点没有任何边的顶点这种顶点会进不了 MAP_DATA或者进了但邻接表是空列表点击时直接报 KeyError。我在验收时还习惯打印一张路径距离表检查距离是否满足三角形不等式。举例南门到图书馆是 180120300 米如果南门到教学楼B的路径绕了 500 米但教学楼B和南门之间没有直接边那 500 米是合理的如果出现了 400 米而直连边 300 米存在就说明算法出 bug 了。这种方法在数据量小时非常有效比抽测几个用例更能发现隐藏问题。演示时的叙事顺序也建议提前设计好先打开程序展示地图底图说明“我把校园建模成了带权无向图”然后点一个起点和一个终点展示路径高亮最后一步也是大多数同学会漏掉的一步——演示“起点等于终点”的情况程序显示红色路径只画一个点或画一条零长度的线。这个边界场景一旦处理正确评审对你好感度会明显提升因为很多人根本没想过这个问题。如果有多余时间还可以做一个统计功能用同一个图统计每个顶点的度邻居数量在界面上把“度1”死胡同的顶点用一种颜色标出来。这看似简单但它把数据结构的“度”概念直接用在了导航图上是一份很好的加分项。我当时的做法是在生成的路径旁显示“途经 X 个节点总路程 Y 米”这个信息由 Dijkstra 返回的路径列表长度自然得出不需要额外计算。最后啰嗦一句我自己的教训不要为了追求界面炫而引入 matplotlib 或 networkx。这些库能画出更好看的图但作业里你无法在答辩现场现场演示安装依赖评审打开你代码跑不起来的风险远大于界面丑的风险。Tkinter 自带的绘制能力足够把这道题讲透。这是我希望你踩的坑不要踩用最少的第三方依赖完成一个完整闭环然后把精力留在 Dijkstra 的分析和边界讨论上希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/11/2 5:52:01 · 阅读 1.2k 基于Python的校园导航：图数据结构与Dijkstra算法完整实现
简介数据结构课程期末项目“基于Python的zzu校园导航”完整实现包面向高校计算机专业学生、课程设计团队及图算法初学者。项目以郑州大学校园为实际场景综合运用DFS/BFS图遍历与Dijkstra、Bellman-Ford最短路径算法完成路径计算基于Tkinter构建交互界面并覆盖地图数据存储、坐标映射与异常处理模块适合作为课程设计参考或算法综合练习素材。压缩包共131个文件整体约7.13MB120张png截图展示各场景界面与运行效果5个Python源码文件为核心实现另有3个pyc编译文件、1份PDF介绍文档、1个中文字体文件及1个附加zip包目录清晰便于按模块学习。已有69人学习下载。资料内含算法思路导图、多场景导航运行截图与完整代码读者既可借此理解图算法从理论到落地的完整链路也可参考界面设计、测试用例与异常处理方式拓展至其他校园或园区导航项目。1. 为什么数据结构期末作业我会选“校园导航”一个好讲清楚图的题目数据结构课期末作业最怕的不是算法难而是题目太虚——写一个图书管理系统全班三十份作业长一个样写一个迷宫求解评审看两分钟就腻。我当年选的是“基于 Python 的 zzu 校园导航”核心原因是它天然对应图论里的最短路径能同时把图的存储结构、遍历方式、Dijkstra 算法和工程封装都摊开讲明白而且演示效果直观在界面里点两个建筑物路径立刻画出来比输出一串数字有说服力得多。这篇笔记就是我当时跑通的完整实现思路从图建模到 GUI 到交作业前的验收适合正被数据结构作业卡住、想选导航类题目又怕做不完的人。你不需要懂复杂的 GIS 知识Python 会写类、会用字典和列表就能跟着复现。2. 把地图变成图zzu 校园导航的数据结构选型与建模2.1 为什么“校园导航”本质上是一个图问题而不是数组问题校园导航要解决的业务问题是给定两个地点比如“图书馆”和“行政楼”找到一条经过的道路总长度最短的路线。这背后有一个很经典的形式化过程——把每个建筑物抽象成顶点Vertex把建筑物之间实际存在的道路抽象成边Edge把道路的长度米作为边的权值Weight于是整个校园就变成了一张带权无向图Weighted Undirected Graph。选这个模型的理由要能在答辩时说出来数据结构课中学的线性表、栈、队列本质都是“一对一”或“一对多”的关系而地图上任意两个地点之间都可能连通这是一种“多对多”的关系只能由图来刻画。图这个结构不是为导航发明的但它恰好能把导航的物理世界映射成程序能处理的数据。这个映射过程有一个专门的说法叫“图建模”Graph Modeling作业评审关心的第一件事往往就是你有没有把真实世界抽象成图的这一步而不是你有没有把 Dijkstra 代码背下来。2.2 邻接表还是邻接矩阵这份作业怎么选依据是什么图的存储方式在数据结构课本里主要有两种邻接矩阵Adjacency Matrix和邻接表Adjacency List。做这个题之前必须先想清楚用哪个因为后面所有算法都建立在存储结构之上。邻接矩阵用二维数组存matrix[i][j]表示顶点 i 到顶点 j 的边的权值连通为具体路程不连通为无穷大。它的优点是判断两个顶点是否相邻是 O(1) 时间缺点是空间复杂度固定为 O(V²)V 是顶点数。校园导航的顶点规模一般在 20 到 50 个之间矩阵也就几百个元素空间完全不是问题。邻接表则用“数组 链表”或“字典 列表”实现每个顶点后面挂一个链表存它能到达的邻居和对应权值。优点是稀疏图下省空间遍历某个顶点的所有邻居时效率高缺点是代码结构稍微复杂一点而且判断两个顶点是否相邻需要遍历链表。我的建议是选邻接表但用 Python 的字典来实现。为什么因为这是期末作业不是工程系统你需要向评审展示“我懂邻接表的原理”而 Python 字典天然就是“顶点 - 邻居列表”的映射代码可读性极高答辩时一句话能讲清楚。更重要的是Dijkstra 算法在邻接表上的实现比邻接矩阵更自然——你只需要遍历当前顶点的邻居不需要扫描一整行矩阵这能让你的算法复杂度分析站得住脚后面会细说。2.3 从零写地图数据把 zzu 的楼和路存成字典建模的第一步是收集数据。我当时是在校园地图上人工数出了 15 个主要节点南门、北门、图书馆、教学楼 A/B/C 栋、行政楼、食堂一/二、体育馆、宿舍区、实验楼、校医院、计算机学院楼等。然后目测或根据校园地图比例尺估算每两个相邻节点间的步行距离米不相邻的节点之间不建边这样得到一张稀疏图。关键设计决策不要试图把任意两个楼都连起来那样图就稠密到失去意义了。真实校园里你从图书馆去食堂一定经过某个路口或某条主路这些中间点也必须建模成顶点。换句话说导航图中的顶点不只是目的地还包括路口、岔路。我当时在主干道上加了 3 个“虚拟路口点”让路径更贴近真实情况代码上完全没增加难度但演示效果和真实感会好很多。# graph.py # 图的邻接表存储字典的 key 是顶点名value 是 (邻居, 距离) 的列表 # 这是手工维护的静态地图数据真实项目可以改用 JSON 或数据库但作业用常量文件就够了 MAP_DATA { 南门: [(行政楼, 180), (实验楼, 240)], 行政楼: [(南门, 180), (图书馆, 120), (教学楼A, 90)], 图书馆: [(行政楼, 120), (教学楼B, 150), (食堂一, 100)], 教学楼A: [(行政楼, 90), (教学楼B, 110), (计算机学院楼, 200)], 教学楼B: [(图书馆, 150), (教学楼A, 110), (教学楼C, 80)], 教学楼C: [(教学楼B, 80), (实验楼, 160), (食堂二, 130)], 实验楼: [(南门, 240), (教学楼C, 160), (校医院, 100)], 计算机学院楼: [(教学楼A, 200), (体育馆, 120)], 体育馆: [(计算机学院楼, 120), (宿舍区, 240)], 宿舍区: [(体育馆, 240), (食堂二, 180), (北门, 260)], 食堂一: [(图书馆, 100), (食堂二, 140)], 食堂二: [(教学楼C, 130), (宿舍区, 180), (食堂一, 140)], 校医院: [(实验楼, 100), (北门, 320)], 北门: [(宿舍区, 260), (校医院, 320)], }这段代码的逻辑说明整个图就是一个个元组组成的列表每个元组是“去往哪个顶点、路程多少米”。注意我把主干道的“路口”也建模成了顶点比如“教学楼B”连接行政楼、图书馆、教学楼A、教学楼C天然承担了路口职能这是导航图建模里非常常见的手法——中间节点不仅给人指路还把图切出层次。参数说明距离单位统一为米不建议混用公里边的权值必须是正数因为 Dijkstra 算法要求非负权如果后期要加“通行时间”作为权值只需要把这个数字换成时间秒数其余逻辑完全不变。自测方法随便选一个顶点数一下它的邻居数量和 MAP_DATA 里对应列表长度一致即可。更严谨一点可以写一个函数验证图的连通性从南门出发遍历所有顶点确保没有孤立节点——这个坑我在避坑章节还会提。3. 导航核心算法Dijkstra 最短路径的实现细节与参数调校3.1 Dijkstra 为什么是这道题的“标准答案”以及它的局限在哪里数据结构课程里讲最短路标准解法就是 Dijkstra 算法。它的核心思想是贪心维护一个“已确定最短距离的顶点集合”S 和一个“未确定顶点到源点的当前最短距离”数组 dist每次从 S 外取出 dist 值最小的顶点 u用 u 去松弛Relax它的所有邻居。所谓松弛就是检查“经过 u 到邻居 v 是否比之前记录的 dist[v] 更短”如果更短就更新。选 Dijkstra 而不选 Floyd 的原因是Floyd 一次算出所有点对之间的最短路代码确实更短三层循环但它的时间复杂度是 O(V³)而且答辩时很难解释“为什么你要算全校任意两点之间的最短路而程序里只需要一对一的导航”。Dijkstra 的单源最短路特性正好匹配导航场景你选一个起点只需要得到这一个源点到所有点的最短路然后取出目标点的那条。Dijkstra 有一个学校教材里不常强调、但实验中一定会碰到的条件图中不能有负权边。负权会破坏贪心选择的正确性因为一旦出现负数之前被判定为“已最短”的路径可能因为一条负权边反而变长。校园导航里的距离都是正数所以安全如果你的期末作业想扩展成“带红绿灯等待时间的导航”这里的等待时间也是非负的依然安全。如果哪天你做一个带“下坡捷径 -5 米”这种诡异数据的图那就得换 Bellman-Ford但这不是本作业范围。3.2 用 Python 手写 Dijkstra最小堆版与代码注释课本上的 Dijkstra 伪代码用数组找最小值复杂度 O(V²)。Python 里更常规的写法是用优先队列heapq 最小堆来维护“当前距离最小的未确定顶点”复杂度能降到 O((VE)logV)E 是边数。这道题的顶点只有十几个V² 完全够用但用堆实现的代码更能体现你对 Python 数据结构的理解——heapq 本身就是一个数据结构知识点答辩时可以顺带讲。# dijkstra.py import heapq def dijkstra(graph, source, target): 基于最小堆的 Dijkstra 最短路算法 :param graph: 邻接表格式同 MAP_DATA :param source: 起点顶点名 :param target: 终点顶点名 :return: (距离, 路径顶点列表)若不存在路径返回 (float(inf), []) # 初始化距离表所有顶点距离为无穷大源点距离为 0 dist {vertex: float(inf) for vertex in graph} prev {vertex: None for vertex in graph} # 记录每个顶点的前驱用于回溯路径 dist[source] 0 # 最小堆里存 (当前距离, 顶点名) heap [(0, source)] while heap: current_dist, current heapq.heappop(heap) # 如果弹出的是某个顶点的过期记录距离不是最新的直接跳过 if current_dist dist[current]: continue # 提前终止当前已经是目标顶点说明最短路已经确定 if current target: break # 松弛当前顶点的所有邻居 for neighbor, weight in graph[current]: new_dist current_dist weight if new_dist dist[neighbor]: dist[neighbor] new_dist prev[neighbor] current heapq.heappush(heap, (new_dist, neighbor)) # 这里不能直接 return因为堆里可能有其他顶点距离更小 # 回溯路径 path [] node target while node is not None: path.append(node) node prev[node] path.reverse() if dist[target] float(inf): return float(inf), [] return dist[target], path这段代码有三个容易被忽略的参数细节我逐一说明。第一个是堆中存储的格式(current_dist, current)Python 的元组比较会先比较第一个元素所以堆会自动按距离排序第二个是“过期记录跳过”的判断if current_dist dist[current]因为同一个顶点可能被加入堆多次老记录在堆底弹出时距离已经比 dist 里的最新值大不跳过会重复松弛虽然结果不错但性能差且逻辑不干净第三个是松弛时的严格不等号new_dist dist[neighbor]这里必须用严格小于如果改成遇到等权路径时 prev 可能被反复更新路径回溯会不稳定——这在作业里不致命但答辩时被问到了会显得基础不牢。3.3 从 dist 数组到完整路径回溯 prev 时最容易写错的一种情况调用上面这个函数时很多人会以为返回的就直接是一条从 source 到 target 的路径测试却发现路径只有两个端点中间楼全丢了。原因出在回溯的终止条件上。我第一次写的时候用的是while node ! source看起来没毛病但如果你给的 target 就是 source起点即终点循环体一次都不执行path 里只有一个 target然后你手动把 path 反转成[target]再往里加 source 就变成[source, target]顺序反了且没有中间节点。正确做法是像上面代码那样prev[source]保持为 None回溯统一用while node is not None作为终止条件。这相当于给回溯画了一条从 target 一路指回 source 的链表None 就是链表的结尾哨兵。如果你坚持要写while node ! source就必须额外处理“起点等于终点”这个分支否则输出结果会是一个空路径或错误路径。我给这段代码加了一个if dist[target] float(inf)的判断处理不连通的情况——虽然我的 MAP_DATA 完全连通但你不保证你自己的数据不出意外保留这个判断是交作业前最省事的自保手段。另一个和路径相关的坑是距离表的初始化float(inf)是 Python 表示正无穷的标准写法不要用一个大整数比如9999999代替。用大整数虽然能跑通但在松弛比较时可能出现“恰好路径总长超过 9999999”这种薛定谔的 bug用 inf 后任何有限数都比它小逻辑上不会出错。至于 prev 的初始值设为 None是为了配合回溯链表的终止判断逻辑上和 source 的 prev 永远是 None 是一致的。4. 让导航看得见用 Tkinter 搭一个能点的校园地图界面4.1 图形界面选 Tkinter 还是 Pygame一份期末作业该怎么取舍导航算法跑通之后只是命令行输出演示效果大打折扣。我当时先试了 Pygame发现它适合做游戏画点、画线、响应鼠标事件都要自己管而且刷新机制是游戏帧循环跟“点击一下出结果”这种交互模式其实不太匹配。后来换成了 Python 自带的 Tkinter理由很朴素它不需要额外安装第三方库任何机器上有 Python 就能跑评审打开你的源码不需要 pip install 任何依赖这对期末作业来说是最重要的优势。Tkinter 的绘图模型是 Canvas画布可以在上面画直线、圆形、文字。这对导航界面够用了建筑物画成带名字的节点圆道路画成连线最短路径高亮画成红色粗线。它的劣势是 UI 样式比较老旧没有现代网页那种圆角和渐变色但作业评审更看重你能否清晰展示数据结构和算法流程不需要精美到产品级。4.2 画底图、布坐标、绑定点击事件一个最小可跑 GUI 骨架Tkinter 里最关键的是“坐标系统”。你需要给每个顶点分配一个 (x, y) 像素坐标然后在地图画布上把这些点连成道路。我的做法是新建一个字典POSITIONS {南门: (100, 600), 行政楼: (150, 480), ...}像素坐标是我对着校园地图按比例缩放的不是精确的经纬度但在作业演示层面形似和路线合理就够用了。# gui.py import tkinter as tk from tkinter import messagebox from graph import MAP_DATA from dijkstra import dijkstra # 每个顶点的画布像素坐标(x, y) POSITIONS { 南门: (100, 600), 行政楼: (150, 480), 图书馆: (250, 360), 教学楼A: (220, 400), 教学楼B: (330, 300), 教学楼C: (420, 260), 实验楼: (380, 420), 计算机学院楼: (300, 220), 体育馆: (450, 120), 宿舍区: (600, 150), 食堂一: (330, 420), 食堂二: (520, 280), 校医院: (500, 480), 北门: (650, 350), } class CampusNavApp: def __init__(self, root): self.root root self.root.title(zzu 校园导航数据结构期末作业) self.canvas tk.Canvas(root, width750, height650, bgwhite) self.canvas.pack(sidetk.LEFT) self.info tk.Label(root, text点击起点再点击终点, font(SimHei, 14)) self.info.pack(sidetk.TOP, filltk.X) self.start None # 正在等待终点时的起点 self._draw_map() # 先画静态底图节点 道路 def _draw_map(self): # 先画所有边道路再画节点保证节点圆盖在线上这样圆里不会被线覆盖 for u in MAP_DATA: x1, y1 POSITIONS[u] for v, _ in MAP_DATA[u]: x2, y2 POSITIONS[v] self.canvas.create_line(x1, y1, x2, y2, fillgray, width2) for name, (x, y) in POSITIONS.items(): self.canvas.create_oval(x - 15, y - 15, x 15, y 15, filllightblue, outlineblack, width2) self.canvas.create_text(x, y, textname, font(SimHei, 10))上面这段代码只实现了静态地图绘制还差点击事件。要点是create_line和create_oval的绘制顺序会互相覆盖先把所有边画完再画节点节点的浅蓝色圆能把道路线遮住视觉上“道路从建筑旁边穿过”而不是“建筑盖在道路十字交叉的正上方”。比例尺参数在 POSITIONS 里调如果你加了新顶点记得在该字典里补齐坐标否则画布会直接报 KeyError。4.3 从“能跑”到“像样”路线高亮与信息面板点击交互的逻辑是第一次点击记录起点第二次点击记录终点并调用 dijkstra把返回路径上的线段改成红色粗线。注意这里有个隐藏问题——Canvas 绘制过的对象不能改颜色要在创建时保存对象的 ID。所以在画静态地图时我需要给每一条道路的create_line返回值存进字典self.edge_ids {(u, v): line_id}路线高亮时找到对应 ID调用itemconfig(line_id, fillred, width4)就能变色。def _on_click(self, event): # 绑定到 canvas 的 Button-1 事件 # 根据点击像素坐标命中最近的顶点 best_name None best_d float(inf) for name, (x, y) in POSITIONS.items(): d (event.x - x) ** 2 (event.y - y) ** 2 if d best_d and d 30 * 30: # 最多偏离节点 30 像素才算命中 best_d d best_name name if best_name is None: self.info.config(text没点中建筑再试一次) return if self.start is None: self.start best_name self.info.config(textf起点{best_name}再点终点) else: end best_name dist, path dijkstra(MAP_DATA, self.start, end) self.show_path(self.start, end, dist, path) self.start None这段代码里“像素命中”用的是欧氏距离平方比较而不是开方因为比较大小不需要真正开根省掉math.sqrt的开销这是一种常见的计算优化习惯虽然这里数据量小体现不出来但在答辩时说出这个理由能体现你对计算细节的敏感。30 像素是命中半径参数我按 750x650 的画布大小调的太大会出现“点了空白处却选中了远处建筑”的误触太小则要精准点击圆中心演示时容易出丑。事件绑定的唯一注意点是 Canvas 上要先设置canvas.bind(Button-1, self._on_click)而且是在创建画布后立刻绑定绑定晚了你点第一次事件永远不会触发。5. 避坑手册zzu 导航作业里最常见的 5 个翻车现场5.1 翻车现场一导入模块就报 ModuleNotFoundError根因是相对路径和运行方式现象在 IDE 里直接右键运行gui.py报错ModuleNotFoundError: No module named dijkstra。或者同学把 zip 解压后双击运行同样报错。原因大多数同学在写作业源码时喜欢把所有文件平铺在同一个文件夹用 IDE 运行时当前工作目录不一定是源码所在目录Python 会把“当前目录”加入模块搜索路径而不是“源码文件所在目录”。平铺文件在 PyCharm 里跑没问题但换个环境或者从 zip 解压后双击运行工作目录变了就找不到模块。解决两个办法任选其一。一是在gui.py顶部加上import sys, os sys.path.append(os.path.dirname(os.path.abspath(__file__)))二是不用模块导入把所有代码合并进一个文件文件名随便但这样做会牺牲模块化。我建议用第一种因为模块拆分本身是数据结构作业的加分项——你可以在答辩时说“我把图的数据、算法、界面分成三个模块分别负责数据层、逻辑层、表现层”。5.2 翻车现场二Dijkstra 输出路径总是缺楼回溯 prev 的初始值设错了现象从“南门”到“教学楼B”程序输出[南门, 教学楼B]但图里明明有“行政楼”这个中间点。原因prev列表的初始化用了{}回溯时从 target 出发一路node prev[node]到 source 时 prev[source] 的值是 None循环停住导致路径丢失了中间的“行政楼”。如果你把 prev 初始化成每个节点的“前驱是它自己”回溯时遇到 source 就 break但 source 自己也被当成了两个节点路径会变成[南门, 行政楼, 南门, 教学楼B]这种重复。解决把 prev 的默认值统一设为 Nonesource 的 prev 保持 None。回溯循环以while node is not None判断反转后正好是从 source 到 target 的完整路径。写完后跑一个“起点到起点”的自测从南门到南门应当输出[南门]和距离 0如果输出空列表或抛 KeyError就是这条边界没处理。5.3 翻车现场三点击地图上的建筑路线画出来却穿墙而过现象在 GUI 界面里点“图书馆”到“体育馆”画出来的高亮道路直接穿过另一个建筑物圆点视觉效果很假。评审看了会质疑你的地图数据不真实。原因这不是算法错误而是“图的结构”和“画的布局”不一致。我在 MAP_DATA 里给“教学楼B”定义了三条边分别通向图书馆、教学楼A、教学楼C但我在界面布局时把教学楼B放在了三个邻居的几何中心附近三条线必然穿过它的圆。真实地图里道路不会穿过建筑物但因为布局是手调的就可能出现这种伪交叉。解决调整布局或调整边。最简单的办法是调整 POSITIONS 坐标让道路绕开节点圆更规范的做法是把真实地图扫描后按坐标描点而不是手动摆位置。我当时折中处理把教学楼B移到画布偏右下让三条边变成类似三角形的三条边穿过感大幅减弱。检查方法逐条遍历所有边检查线段与节点圆心之间的距离是否小于节点半径15 像素如果小于就输出警告。这种自检代码写几行就能做但很少有人做属于典型的“验收前不看整体图”的失误。5.4 翻车现场四zip 包发过去评审解压后运行直接闪退现象源码在自己电脑跑得好好的交压缩包后对方一运行窗口一闪而过根本看不到界面或直接报TclError: no display之类的错。原因有两种典型情况。第一种是你运行时没加root.mainloop()或者你的代码里把mainloop写到了某个函数内部而不是最外层导致窗口创建后立即销毁。第二种是压缩包里包含了你本机的绝对路径比如你导入了位于D:/myproject/campus_nav下的资源文件而评审解压到了桌面路径失效。解决交作业前用“解压后换个目录运行”的方式自测至少一遍。具体操作把原文件夹复制到一个完全不相干的路径比如C:/tmp/下解压 zip然后运行。如果窗口能正常弹出说明路径适配没问题。还有一个很容易被忽略的点Tkinter窗口里控件字体如果你指定了font(SimHei, 14)当评审机器没有中文字体时控件会显示方框。保险做法是在代码里做一次字体探测找不到宋体就回退到默认字体import tkinter.font as tkfont try: tkfont.Font(familySimHei) except tk.TclError: info_font (Arial, 14) # 回退字体5.5 翻车现场五算法跑得慢界面一卡一卡原因是你把搜索放在了主线程现象点完终点之后界面卡住几十毫秒到几秒不等像死机一样然后突然出结果。顶点多的时候更明显。原因Tkinter 的mainloop是单线程事件循环你的 Dijkstra 计算如果直接在鼠标事件回调里执行会阻塞事件循环期间界面无法重绘、无法响应鼠标直到算法返回。虽然你的图只有十几个顶点Dijkstra 运行时间在毫秒级但卡片现象依然存在因为中间还有路径高亮的重绘操作。解决这个图规模完全不需要开线程最简单的优化是不做耗时操作。你只需要在点击终点后先更新状态文本为“计算中…”然后立刻调用self.root.update()强制刷新一次画面再执行算法最后画路径。update()是 Tkinter 里非常实用的一个低频 API它能让事件循环在长任务期间依然处理部分重绘请求。如果哪天真要扩展到全校几百个楼那就改用threading.Thread开一个后台线程执行 Dijkstra界面线程只负责接收结果画线。期末作业能用update()解决就够用了开线程反而要处理线程安全复杂度陡增。6. 交作业前做一轮自验收检查连通性、边界路径和演示话术验收的第一步写一个命令行自测脚本脱离界面直接验证算法正确性。做法是遍历所有顶点对分别调用 dijkstra把每一对的路径打印出来肉眼扫一遍有没有“断头路”或“绕远路”。这里有一个很容易忽略的边界情况——图不是强连通图比如从“北门”到“南门”可能要走很远但只要路径存在就不算错真正的问题是有孤立顶点没有任何边的顶点这种顶点会进不了 MAP_DATA或者进了但邻接表是空列表点击时直接报 KeyError。我在验收时还习惯打印一张路径距离表检查距离是否满足三角形不等式。举例南门到图书馆是 180120300 米如果南门到教学楼B的路径绕了 500 米但教学楼B和南门之间没有直接边那 500 米是合理的如果出现了 400 米而直连边 300 米存在就说明算法出 bug 了。这种方法在数据量小时非常有效比抽测几个用例更能发现隐藏问题。演示时的叙事顺序也建议提前设计好先打开程序展示地图底图说明“我把校园建模成了带权无向图”然后点一个起点和一个终点展示路径高亮最后一步也是大多数同学会漏掉的一步——演示“起点等于终点”的情况程序显示红色路径只画一个点或画一条零长度的线。这个边界场景一旦处理正确评审对你好感度会明显提升因为很多人根本没想过这个问题。如果有多余时间还可以做一个统计功能用同一个图统计每个顶点的度邻居数量在界面上把“度1”死胡同的顶点用一种颜色标出来。这看似简单但它把数据结构的“度”概念直接用在了导航图上是一份很好的加分项。我当时的做法是在生成的路径旁显示“途经 X 个节点总路程 Y 米”这个信息由 Dijkstra 返回的路径列表长度自然得出不需要额外计算。最后啰嗦一句我自己的教训不要为了追求界面炫而引入 matplotlib 或 networkx。这些库能画出更好看的图但作业里你无法在答辩现场现场演示安装依赖评审打开你代码跑不起来的风险远大于界面丑的风险。Tkinter 自带的绘制能力足够把这道题讲透。这是我希望你踩的坑不要踩用最少的第三方依赖完成一个完整闭环然后把精力留在 Dijkstra 的分析和边界讨论上希望帮到你。本文还有配套的精品资源点击获取