最短路径dijkstra算法

Dijkstra算法是一种用于解决单源最短路径问题的经典算法。它可以找到一个节点到所有其他节点的最短路径。

算法的基本思想是：从起始节点开始，逐步扩展到其他节点，通过确定当前节点到其他节点的最短路径来更新节点的最短距离。具体步骤如下：

1. 创建一个距离数组dist[]，用于存储起始节点到每个节点的最短距离。初始时，将起始节点的距离设置为0，其他节点的距离设置为无穷大。
2. 创建一个集合visited，用于存储已经确定最短路径的节点。
3. 重复下面的步骤，直到visited集合包含所有节点：
a. 从未访问节点中选择距离起始节点最近的节点，将其标记为visited。
b. 更新与该节点相邻节点的距离。对于每个相邻节点，如果通过当前节点到达该节点的距离小于dist[]中已有的最短距离，则更新距离值。
4. 最终，dist[]数组中存储的就是起始节点到每个节点的最短距离。

这样，通过Dijkstra算法可以得到起始节点到其他所有节点的最短路径。

需要注意的是，Dijkstra算法在处理带有负权边的图时可能会出现问题，因为它假设所有边的权重都是非负的。如果图中存在负权边，可以考虑使用其他算法，如Bellman-Ford算法或者SPFA算法。