2017中兴捧月算法精英挑战赛Dijstra提交报告

【算法报告概述】 这篇报告是关于2017年中兴捧月算法精英挑战赛的参赛作品，作者在比赛中获得了中南赛区的区域优胜奖。报告主要介绍了一个使用Dijkstra算法解决特定问题的实现，该问题是寻找经过指定特殊点和特殊边的最短路径。 【算法原理】 算法的核心是Dijkstra算法，它是一种用于查找图中两点之间最短路径的常用方法。在本问题中，算法需要处理包含特殊点和特殊边的约束。定义特殊点（和）和特殊边（）。算法的基本策略是先确定特殊点和特殊边的访问顺序，然后计算每种可能排列下的最短路径，最后将这些路径拼接成从起点到终点的完整路径。 1. 确定特殊点访问顺序：检查特殊点是否是特殊边的端点，避免重复考虑。对于剩下的特殊点，生成所有可能的访问顺序。 2. 插入特殊边：根据特殊点的访问顺序，将所有特殊边插入到排列中，形成完整的访问顺序。 3. 计算最短路径：对每个排列，使用Dijkstra算法计算相邻特殊点或特殊边的最短路径。同时进行剪枝操作，如果路径节点数超过限制，则停止计算。 4. 拼接路径：将相邻特殊点或特殊边的最短路径组合，得到完整路径。 【算法实现与结果分析】 算法在不同拓扑图上进行了实验，使用TXT文件存储数据。实验步骤包括： 1. 求特殊点全排列，生成所有可能的特殊点/特殊边的访问顺序。 2. 插入特殊边，计算需要遍历的排列数量。 3. 应用Dijkstra算法计算相邻特殊点或特殊边的最短路径。 4. 拼接路径，得到最终的完整路径。 实验结果显示，算法能够处理各种情况，包括没有满足条件的路径、存在满足条件的路径以及目标节点不可达的情况。随着特殊边数量的增加，算法的复杂度也会相应提高。 【总结】 这篇报告详尽地展示了如何结合Dijkstra算法解决带有特殊点和特殊边约束的最短路径问题。通过全排列和剪枝策略，算法能够在多种可能的路径中找到满足条件的最优或次优解。这个解决方案不仅适用于中兴捧月算法挑战赛的问题，也可以推广到其他需要寻找受限最短路径的实际问题中。