基于 Dijkstra 与 A* 算法的路径规划系统
一、项目简介
本项目是一个基于 Java Swing 开发的图形化路径规划系统，主要用于模拟校园地图中的最短路径查询。系统将校园中的地点抽象为图中的节点，将道路抽象为带权边，通过 Dijkstra 算法和 A* 算法完成从起点到终点的路径搜索。
项目不仅实现了基础的最短路径查询功能，还加入了图形化地图显示、路径高亮、算法对比、SQLite 数据库存储、路径查询历史记录以及大规模图性能测试等功能。通过该项目，可以比较传统 Dijkstra 算法和带启发函数的 A* 算法在不同场景下的搜索效率差异。
二、项目 Git 地址
https://github.com/TheSnowWolf/PathPlanningSystem三、开发环境与技术栈
| 类型 | 内容 |
|---|---|
| 开发语言 | Java |
| 图形界面 | Java Swing |
| 数据库 | SQLite |
| 数据库连接 | SQLite JDBC |
| JDBC 依赖 | sqlite-jdbc-3.53.2.0.jar |
| 核心算法 | Dijkstra、A* |
| 图结构存储 | 邻接表 |
| 数据结构 | HashMap、LinkedHashMap、PriorityQueue、ArrayList |
| IDE | IntelliJ IDEA |
| 版本管理 | Git、GitHub |
四、项目需求分析
1. 基本功能需求
系统需要实现以下功能：
- 显示校园地图中的地点和道路；
- 用户可以选择起点和终点；
- 用户可以选择使用 Dijkstra 或 A* 算法进行寻路；
- 系统能够显示最短路径、总距离、访问节点数和运行耗时；
- 地图中能够高亮显示最终路径；
- 支持清除当前路径结果；
- 支持 Dijkstra 和 A* 的算法对比；
- 支持将地图数据保存到数据库；
- 支持从数据库读取地图数据；
- 支持保存、查看和清空历史路径查询记录；
- 支持大规模测试数据，用于体现不同算法的性能差异。
2. 非功能需求
- 界面操作简单，适合课程设计演示；
- 代码结构清晰，按 model、algorithm、service、database、ui 等包进行划分；
- 算法模块具有一定扩展性，后续可以继续加入 Floyd、BFS 等算法；
- 数据持久化清晰，地图和历史记录均可保存；
- 对异常输入进行基本处理，例如节点不存在、负权边等情况。
五、系统总体设计
系统整体采用分层设计，大致可以分为以下几层：
Main│├── database 数据库层│ ├── DBUtil│ ├── GraphDao│ └── RecordDao│├── model 数据模型层│ ├── Node│ ├── Edge│ ├── Graph│ └── PathResult│├── algorithm 算法层│ ├── PathAlgorithm│ ├── AbstractSearchAlgorithm│ ├── Dijkstra│ └── AStar│├── service 业务层│ └── RouteService│├── ui 界面层│ ├── MainFrame│ ├── MapPanel│ ├── ControlPanel│ ├── ResultPanel│ └── RecordDialog│└── benchmark 性能测试层 ├── AlgorithmBenchmarkMain └── BenchmarkGraphFactory系统启动流程如下：
程序启动↓初始化 SQLite 数据库↓如果数据库为空，插入默认校园地图数据↓从 nodes 表和 edges 表读取数据↓构造 Graph 对象↓创建 RouteService↓打开 Swing 主窗口↓用户选择起点、终点和算法↓执行寻路并显示结果UML类图
六、核心数据模型设计
1. Node 节点类
Node 用来表示地图中的地点，例如南门、图书馆、教学楼、食堂等。
主要属性包括：
| 属性 | 含义 |
|---|---|
| id | 节点编号 |
| name | 地点名称 |
| x | 横坐标 |
| y | 纵坐标 |
其中坐标不仅用于地图绘制，也用于 A* 算法计算启发函数。
2. Edge 边类
Edge 表示两个地点之间的道路。
主要属性包括：
| 属性 | 含义 |
|---|---|
| from | 起点编号 |
| to | 终点编号 |
| weight | 道路权重，也就是距离 |
3. Graph 图结构类
Graph 负责存储整个地图结构。项目中使用邻接表存储图：
节点编号 -> 从该节点出发的所有边邻接表相比邻接矩阵更节省空间，尤其适合校园道路这种边数远小于完全图的场景。
图结构支持：
- 添加节点；
- 添加有向边；
- 添加无向边；
- 查询某个节点的所有出边；
- 查询所有节点；
- 检查非法节点；
- 检查负权边。
由于 Dijkstra 和 A* 都不能正确处理负权边，因此系统在添加边时会对负权边进行拦截。
七、核心算法设计
1. Dijkstra 算法
Dijkstra 算法是一种经典单源最短路径算法，适用于边权非负的图。
基本思想是：
- 从起点开始，将起点距离设为 0；
- 每次从优先队列中取出当前距离最小的节点；
- 对该节点的所有邻接边进行松弛；
- 不断更新其他节点到起点的最短距离；
- 通过 prev 记录路径前驱；
- 到达终点后回溯得到完整路径。
在本项目中，Dijkstra 被看作启发函数为 0 的 A* 算法，因此可以复用 A* 的主体搜索模板。
2. A* 算法
A* 算法在 Dijkstra 的基础上加入启发函数，优先搜索更可能接近终点的方向。
A* 的优先级计算公式为：
f(n) = g(n) + h(n)其中：
| 符号 | 含义 |
|---|---|
| g(n) | 从起点到当前节点的实际距离 |
| h(n) | 当前节点到终点的估计距离 |
| f(n) | 节点的综合优先级 |
本项目中，A* 使用欧几里得距离作为启发函数：
h(n) = sqrt((x1 - x2)^2 + (y1 - y2)^2)因为地图节点本身带有坐标，所以使用欧几里得距离可以让 A* 更倾向于朝终点方向搜索。
3. 抽象算法模板设计
项目中没有把 Dijkstra 和 A* 完全写成两份重复代码，而是设计了一个 AbstractSearchAlgorithm 抽象父类。
父类中完成通用逻辑：
- 初始化距离表；
- 创建优先队列；
- 访问节点；
- 松弛边；
- 记录前驱；
- 回溯路径；
- 统计访问节点数和耗时。
Dijkstra 和 A* 只需要分别实现自己的启发函数：
// Dijkstrah(n) = 0
// A*h(n) = 欧几里得距离这样可以减少重复代码，也让算法结构更加清晰。
八、数据库设计
项目使用 SQLite 作为本地数据库，数据库文件为：
campus_path.db本项目使用 SQLite 作为本地数据库，需要 SQLite JDBC 驱动支持。
当前项目使用的依赖文件为：
lib/sqlite-jdbc-3.53.2.0.jar数据库主要包含三张表。
1. nodes 表
用于保存地图节点。
| 字段 | 含义 |
|---|---|
| id | 节点编号 |
| name | 节点名称 |
| x | 横坐标 |
| y | 纵坐标 |
2. edges 表
用于保存地图道路。
| 字段 | 含义 |
|---|---|
| id | 道路编号 |
| from_id | 起点节点编号 |
| to_id | 终点节点编号 |
| weight | 道路长度 |
3. path_records 表
用于保存路径查询历史记录。
| 字段 | 含义 |
|---|---|
| id | 记录编号 |
| algorithm_name | 使用的算法 |
| start_node | 起点名称 |
| end_node | 终点名称 |
| distance | 路径总距离 |
| path | 路径文本 |
| visited_count | 访问节点数 |
| time_cost_ms | 耗时 |
| created_at | 查询时间 |
系统启动时会自动检查数据库。如果节点表为空，会自动插入一组默认校园地图数据，方便首次运行和演示。
九、界面设计
项目使用 Java Swing 实现图形化界面，主窗口由以下几个部分组成：
主窗口 MainFrame│├── 左侧控制区 ControlPanel│ ├── 起点选择│ ├── 终点选择│ ├── 算法选择│ ├── 开始寻路│ ├── 清除路径│ └── 算法对比│├── 中间地图区 MapPanel│ ├── 绘制节点│ ├── 绘制道路│ ├── 绘制权重│ └── 高亮最短路径│└── 底部结果区 ResultPanel ├── 显示算法名称 ├── 显示路径总距离 ├── 显示访问节点数 ├── 显示运行耗时 └── 显示完整路径菜单栏包含：
文件├── 从数据库读取地图├── 保存地图到数据库└── 退出
路径├── 开始寻路├── 清除路径└── 算法对比
记录├── 查看历史记录└── 清空历史记录
帮助├── 使用说明└── 关于十、主要功能展示
1. 主界面展示
在主界面中，左侧为操作面板，中间为校园地图，底部为路径结果显示区域。
2. 路径查询展示
选择起点、终点和算法后，点击“开始寻路”，系统会计算最短路径，并在地图上使用红色高亮显示路径。
3. 算法对比展示
点击“算法对比”后，系统会分别运行 Dijkstra 和 A*，并显示两种算法的总距离、耗时、访问节点数和路径。
4. 历史记录展示
系统会将每一次路径查询保存到 SQLite 数据库中，可以通过“记录 -> 查看历史记录”打开历史记录窗口。
5. Git 提交记录截图
十一、算法性能测试
为了更明显地体现 Dijkstra 和 A* 的性能差异，项目额外加入了 benchmark 测试模块。
测试图采用八方向网格图：
- 每个节点最多连接周围 8 个方向；
- 横向、纵向边权为 1；
- 对角线边权为
sqrt(2)； - 起点为左上角；
- 终点为右下角；
- A* 使用欧几里得距离作为启发函数。
测试规模包括：
100 x 100200 x 200300 x 300500 x 5001000 x 1000运行方式：
直接运行 AlgorithmBenchmarkMain 类也可以通过命令行参数指定规模：
AlgorithmBenchmarkMain 500 500该测试不经过 Swing 界面和 SQLite 数据库，只测试算法本身性能。
性能测试样例
性能差异原因
Dijkstra 算法不知道终点方向，会从起点向周围均匀扩散搜索。
A* 算法会利用坐标启发函数，优先搜索更接近终点方向的节点。
因此，在大规模网格图中，A* 通常会访问更少节点，搜索方向也更加明确，性能优势更加明显。
十二、项目亮点
1. Dijkstra 与 A* 共用搜索模板
项目将两种算法的公共逻辑抽象到 AbstractSearchAlgorithm 中，Dijkstra 只需要返回 0 作为启发函数，A* 返回欧几里得距离作为启发函数。
这样既减少了重复代码，也让两种算法的关系更加清晰。
2. 支持图形化地图展示
系统可以绘制节点、道路、边权，并在寻路完成后高亮显示路径，相比纯控制台输出更直观。
3. 支持算法对比
系统不仅可以单独执行某一种算法，还可以同时运行 Dijkstra 和 A*，比较它们的访问节点数和运行耗时。
这使项目不仅是一个路径查询工具，也具有一定的算法分析功能。
4. 支持 SQLite 数据持久化
项目使用 SQLite 保存地图数据和路径查询历史记录。
地图数据可以从数据库读取，也可以保存回数据库；路径查询结果也会自动写入历史记录表中，方便后续查看。
5. 使用 SwingWorker 避免界面卡死
在较大规模地图或算法耗时较长时，如果直接在 Swing 事件线程中运行算法，界面可能会无响应。
项目中使用 SwingWorker 将寻路任务放到后台线程中执行，算法完成后再更新界面，从而提升了用户体验。
6. 加入大规模 Benchmark 测试
普通校园地图节点较少，Dijkstra 和 A* 的耗时差异不明显。
项目中额外设计了大规模八方向网格图测试，可以更清楚地体现 A* 启发函数带来的搜索效率提升。
十三、开发过程中遇到的问题与解决方案
1. Dijkstra 与 A* 代码重复问题
最初如果分别实现 Dijkstra 和 A*，会出现大量重复代码，例如优先队列、距离表、前驱记录和路径回溯等逻辑。
解决方式是提取 AbstractSearchAlgorithm 抽象父类，让两个算法只关注启发函数差异。
2. 无向边重复绘制问题
数据库中无向边实际保存为两条有向边：
a -> bb -> a如果直接遍历所有边绘制，会导致同一条道路被重复绘制。
解决方式是在绘图时使用边的唯一 key，例如：
minId-maxId从而保证每条无向边只绘制一次。
3. 大规模地图下界面卡顿问题
算法运行如果直接放在按钮事件中，会阻塞 Swing 的事件分发线程，导致窗口卡顿。
解决方式是使用 SwingWorker，在后台执行算法，完成后再更新地图和结果面板。
4. 数据库初始化问题
为了让程序首次运行时也能直接展示地图，系统在启动时会检查数据库是否为空。
如果 nodes 表为空，就自动插入默认校园节点和道路数据。
十四、个人负责内容
本项目为个人课程设计项目，主要完成内容包括：
| 模块 | 主要内容 |
|---|---|
| 图结构建模 | 设计 Node、Edge、Graph、PathResult 等数据模型 |
| 算法实现 | 实现 Dijkstra、A* 以及抽象搜索模板 |
| 业务封装 | 使用 RouteService 统一管理算法调用 |
| 图形界面 | 使用 Java Swing 实现主窗口、地图面板、控制面板和结果面板 |
| 数据库 | 使用 SQLite 保存地图数据和路径查询历史记录 |
| 历史记录 | 实现路径记录保存、查看、刷新和清空 |
| 性能测试 | 构造大规模八方向网格图，对比 Dijkstra 与 A* 性能 |
| 版本管理 | 使用 Git 和 GitHub 进行项目版本管理 |
十五、项目总结
本项目完成了一个基于 Java Swing 的路径规划系统，实现了从图结构建模、最短路径算法、图形化显示到数据库持久化的一整套流程。
通过本项目，我主要完成了以下内容：
- 学习并实现了 Dijkstra 和 A* 两种最短路径算法；
- 理解了 A* 启发函数对搜索方向和性能的影响；
- 使用邻接表完成了图结构建模；
- 使用 Java Swing 完成了可视化界面；
- 使用 SQLite 实现了地图数据和历史记录持久化；
- 使用 SwingWorker 优化了大规模计算时的界面响应；
- 通过 Benchmark 模块对两种算法进行了性能测试。
整体来看，本项目不仅完成了课程设计对图形界面、数据库和算法功能的要求，也进一步加深了我对图论算法、Java 面向对象设计和桌面应用开发的理解。
十六、后续改进方向
后续如果继续完善，可以考虑以下方向：
- 支持用户在界面中新增、删除、拖动节点；
- 支持用户手动添加道路和修改边权；
- 增加 Floyd、BFS、Bellman-Ford 等更多算法；
- 增加障碍物或不可通行道路设置；
- 支持导入真实地图数据；
- 增加更美观的 UI 样式；
- 将项目改造成 Web 版本；
- 增加路径动画演示效果。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时