地接斯特拉算法的原理

地接斯特拉算法（Dijkstra's algorithm）是一种用于解决单源最短路径问题的图算法，由荷兰计算机科学家艾兹赫尔·斯特拉于1956年提出。该算法是基于贪心策略的算法，通过逐步构建最短路径树来找到起点到图中所有其他顶点的最短路径。

算法的原理如下：

1. 创建一个距离数组dist，用于存储起点到各顶点的最短路径长度，初始化为无穷大，起点的距离设为0。

2. 创建一个集合visited，用于存储已经找到最短路径的顶点。

3. 从起点开始，遍历图中的所有顶点，选择距离起点最近的未访问顶点作为当前顶点。

4. 更新当前顶点的邻居顶点的最短路径长度。如果从起点到当前顶点的距离加上当前顶点到邻居顶点的距离小于邻居顶点的最短路径长度，则更新邻居顶点的最短路径长度。

5. 将当前顶点标记为已访问，并将其加入visited集合。

6. 重复步骤3到步骤5，直到所有顶点都被标记为已访问。

7. 最后，dist数组中存储的就是起点到每个顶点的最短路径长度。

该算法的关键在于每次选择距离起点最近的顶点，并通过动态更新邻居顶点的最短路径长度来逐步构建最短路径树。通过不断迭代，算法能够找到起点到图中所有其他顶点的最短路径