张博康算法设计：第四章 路径优化问题与Dijkstra算法实现

这段代码是关于“算法设计与分析”课程中的一个部分，具体讨论了第四章的内容，由学生张博康（学号2014211383，班级2014211309）编写。该章节涉及一种路径查找或最短路径问题的解决方案，通过实现Dijkstra算法来寻找两点之间的最短距离。代码中定义了几个关键数据结构： 1. **Station** 结构体表示地理坐标，包含节点ID（long long型），经度和纬度（double型），以及一个整数索引。 2. **Node** 结构体用于表示树的节点，包含左子节点、右子节点引用、权重（int型）和字符（char型）。 3. **Edge** 结构体表示图中的边，由两个节点的编号（u和v，int型）、边的成本（double型）组成，并重载了比较运算符 `<` ，使得可以根据成本进行排序。 4. 使用了标准库中的多种头文件，如iostream、sstream、fstream、cstring、cstdlib、vector等，以及climits、cmath、queue、map和algorithm，这些库提供了输入输出操作、字符串处理、文件操作、整数限制、数学函数、队列操作、关联容器和算法支持。 代码的关键部分是 `distance` 函数，它计算两点之间的大圆距离（Haversine公式），考虑了地球的曲率。此外，`dp`、`opr` 和 `weight` 数组用于Dijkstra算法的动态规划，`father` 数组记录了每个节点的父节点，而 `distance` 函数在算法中被多次调用以更新最短路径。 Dijkstra算法的主要步骤包括初始化距离数组、选择当前未访问的最小距离节点、更新相邻节点的距离并标记已访问，直到找到终点或者所有节点都被访问。这段代码是实现Dijkstra算法的基础框架，适用于解决图中两点之间最短路径的问题。 总结起来，这个源代码展示了如何在实际编程环境中应用算法设计理论，尤其是Dijkstra算法在地理信息系统（GIS）中的应用，用于计算地球上两个位置之间的最短路径。通过这段代码，学生可以深入理解算法的工作原理，并将其应用到实际问题中。