Dijkstra 算法

Dijkstra算法是一种用于解决图中最短路径问题的算法。它由荷兰计算机科学家Edsger Dijkstra在1956年提出。该算法通过求解从起点到所有其他顶点的最短路径，找到图中的最短路径。

该算法的基本思想是从起点开始，逐步扩展搜索范围，直到找到目标顶点或者搜索完所有顶点。在每一步中，选择当前距离起点最近的顶点，并根据该顶点更新与其相邻顶点的距离。

Dijkstra算法的具体步骤如下：
1. 创建一个距离表，记录起点到每个顶点的当前最短距离（初始时将起点的距离设为0，其他顶点的距离设为无穷大）。
2. 创建一个集合，用于记录已经找到最短路径的顶点。
3. 重复以下步骤直到所有顶点都被加入集合：
- 从距离表中选择当前距离起点最短的顶点，并将其标记为已访问。
- 更新与该顶点相邻的顶点的距离，如果通过当前顶点到达相邻顶点的路径更短，则更新距离表中该顶点的距离值。
4. 最终距离表中记录的即为起点到各个顶点的最短距离。

Dijkstra算法通常用于解决无负权边的最短路径问题，可以应用于很多实际场景，如路由算法、地图导航等。