实验名称： 基于图结构的最短路径算法应用与分析
课程名称： 数据结构
实验日期： 2023年11月15日
提交日期： 2023年11月22日
学生姓名： 李明
学号：
专业班级： 计算机科学与技术2023级1班
一、实验目的
1. 深入理解图结构的基本概念、存储表示（邻接矩阵、邻接表）及其特性。
2. 掌握Dijkstra算法与Floyd算法的核心思想、实现步骤及算法复杂度。
3. 通过实际编程实现，分析两种算法在不同规模图数据上的性能差异，并探讨其适用场景。
4. 将算法应用于模拟的校园导航场景，验证其解决实际问题的有效性。
二、实验原理
1. 图结构：图G由顶点集V和边集E组成，本次实验主要涉及带权有向图。
2. 存储结构：采用邻接矩阵和邻接表两种方式实现图的存储。邻接矩阵适用于稠密图，便于快速判断任意两顶点间连通性；邻接表适用于稀疏图，节省存储空间。
3. Dijkstra算法：一种用于求解单源最短路径的贪心算法。它维护一个已确定最短距离的顶点*S，逐步扩充S，每次从未确定顶点中选取距离源点最近的顶点加入S，并松弛其邻接边。时间复杂度为O(|V|²)（使用邻接矩阵且简单查找最小距离顶点）或O(|E|log|V|)（使用优先队列优化）。
4. Floyd算法：一种动态规划算法，用于求解所有顶点对之间的最短路径。通过三重循环，逐步考虑每个顶点作为中间点，更新任意两点间的最短距离估计。时间复杂度为O(|V|³)，空间复杂度为O(|V|²)。
三、实验环境
四、实验内容与步骤
1. 数据结构定义：
2. 算法实现：
3. 测试用例设计：
4. 性能对比：
5. 应用模拟：
五、实验结果与分析
1. 运行结果正确性：
2. 性能数据分析：
Dijkstra：适用于求解单个或少数几个源点到其他所有点的最短路径问题，尤其是在稀疏图中使用优先队列优化后效率很高。本次实验的校园导航（固定起点）适合使用此算法。
Floyd：适用于需要频繁查询任意两点间最短路径的场景，且图规模不宜过大（顶点数几百以内）。其代码简洁，对于一次性预处理所有路径需求的场景更合适。
3. 应用实例分析：
六、遇到的问题及解决方法
1. 问题：初始化Floyd算法的路径记录矩阵时，最初直接使用-1表示不可达，导致在路径回溯时逻辑复杂。
解决：改为使用顶点的前驱顶点编号进行记录，不可达处初始化为`None`，使路径还原逻辑更清晰。
2. 问题：Dijkstra算法中，需要频繁查找当前未访问顶点中距离最小的顶点，最初使用线性扫描，效率较低。
解决：对于当前实验规模，线性扫描可接受。但认识到在实际大规模应用中，应使用最小堆（优先队列）来优化此步骤，可将查找最小值的复杂度从O(|V|)降至O(log|V|)。
七、实验结论
本次实验成功实现了图的两种存储结构、Dijkstra单源最短路径算法和Floyd全源最短路径算法。通过模拟数据测试，验证了算法的正确性。性能对比分析表明，Dijkstra算法在解决单源问题时有优势，而Floyd算法在需要全源信息时更为方便，但其立方级时间复杂度限制了在大规模图上的应用。实验将理论算法与“校园导航”应用场景结合，加深了对图结构及其经典算法实用价值的理解。未来可进一步尝试实现基于邻接表和优先队列的Dijkstra算法优化版本，并应用于更复杂、真实的道路网络数据。
附录：核心代码（部分）