Dijkstra最短路径规划算法实现

资 源 简 介

本项目是专为MATLAB 6.0 (R12)老版本环境定制开发的Dijkstra最短路径规划算法。其核心功能是解决加权图中单源最短路径问题，能够高效计算出从起始节点到网络中所有其他节点或特定目标节点的最短距离及完整路由序列。

详 情 说 明

基于 MATLAB 6.0 (R12) 的 Dijkstra 最短路径规划系统

项目介绍

本项目是一个专门针对旧版本 MATLAB 环境（如 R12 版本）优化设计的 Dijkstra 最短路径规划工具。该工具旨在解决加权图中的单源最短路径问题，能够准确计算出网络中起点到终点的最小权值之和，并清晰地展示具体的路由跳转序列。通过结合数值计算与图形化显示，项目为网络拓扑分析和路径规划研究提供了一个直观且可靠的实现方案。

功能特性

• 单源最短路径搜索：实现经典的 Dijkstra 算法，计算起始节点到目标节点的最短距离。
• 路径序列自动提取：通过前驱节点追溯机制，完整还原出最短路径经过的所有节点顺序。
• 环境兼容性优化：代码逻辑严格遵循旧版 MATLAB 语法规范，采用大数值常数处理无穷大连通性，确保在 R12 等低版本环境中的运行稳定性。
• 动态图形化可视化：程序会自动生成拓扑图，通过不同颜色区分起点、终点、路径节点及普通节点。
• 权值与拓扑展示：在图形界面中实时标注节点编号及边权值，并以加粗红线突出显示最终的最短路径。

实现逻辑与算法细节

1. 环境与数据初始化 程序首先清理工作区内存并关闭多余窗口。通过一个 7x7 的邻接矩阵来定义图的拓扑结构，其中矩阵元素的值代表节点间的边权。为了适配老版本环境，使用特定的较大数值（如 9999）来表征节点间的不连通性，而 0 则表示节点自身的距离。

2. 核心算法流程 程序采用经典 Dijkstra 算法逻辑，维持三个核心数组：

• 距离数组 (dist)：存储从起点到当前每个节点的最短已知距离。
• 前驱记录 (prev)：记录每个节点路径上的上一个节点，用于后续路径回溯。
• 访问状态 (visited)：标记节点是否已确定最短路径。

算法通过两层循环执行：

• 节点选取：在所有未访问的节点中，寻找当前距离起点最近的节点作为当前处理节点。
• 松弛操作 (Relaxation)：遍历当前处理节点的所有邻接点，计算如果经过该点到达邻接点是否会产生更短的距离。如果是，则更新距离数组并修改前驱记录。

3. 路径序列还原 在计算完成后，程序从终点 node 开始，利用前驱记录数组逐级向起点方向进行回溯，最终将回溯得到的节点序列倒映射，从而提取出从起点到终点的正向路由路径。

4. 结果输出与图形渲染

• 命令行输出：程序在控制台打印计算得到的最短总权值，并以“节点 -> 节点”的格式显示完整的路由序列。
• 图形化渲染：

- 使用坐标映射技术，通过直线绘制节点间的物理连通关系。 - 在连线的中心位置通过文本标注显示边的权值。 - 通过节点颜色编码增强可读性：绿色表示起点，红色表示终点，橙色表示最短路径经过的中间节点，蓝色表示普通节点。 - 最终的计算结果会作为图表标题动态更新，展示总权重信息。

系统要求

• 软件环境：MATLAB 6.0 (R12) 或更高版本。
• 硬件要求：支持基础图形窗口显示的通用计算机设备。

使用方法

1. 在 MATLAB 环境中运行代码脚本。
2. 程序将自动加载预设的 7 节点图拓扑结构。
3. 计算完成后，MATLAB 命令窗口将显示最短路径长度及路径序列。
4. 程序将自动弹出可视化窗口，展示包含节点、权值及红色标注的最短路径路线图。
5. 如需修改拓扑或搜索目标，可直接调整代码中的邻接矩阵、起点（start_node）及终点（end_node）参数。