Dijkstra(迪杰斯特拉)算法是一种用于寻找带权重图中的最短路径的算法。它由荷兰计算机科学家Edsger Dijkstra于1956年提出，被广泛应用于网络路由算法和地图路线规划等领域。
算法思想：
- 初始化一个距离数组，用于保存起点到每个顶点的当前最短距离（初始时将起点距离设置为0，其他顶点距离设置为无穷大）
- 创建一个集合S，用于保存已经找到最短路径的顶点
- 重复以下步骤，直到集合S包含所有顶点：
- 从未包含在集合S中的顶点中，选择距离起点最短的顶点v
- 将顶点v添加到集合S中
- 对于v的每个邻接顶点u，如果通过v可以缩短起点到顶点u的距离，则更新距离数组中u的距离值为起点到v的距离加上v到u的边的权重
优点：
- Dijkstra算法能够找到起点到各个顶点的最短路径，确保解的正确性。
- 算法的时间复杂度较低，对于稠密图和稀疏图都能够高效地求解最短路径问题。
缺点：
- 算法要求图中边的权重必须为非负数，否则结果可能不正确。
- 当图的规模较大时，Dijkstra算法的时间复杂度较高，不适合处理规模较大的问题。
以下是使用C++语言实现Dijkstra算法的示例代码：
#include <io