最短路径算法-迪杰斯特拉(Dijkstra)算法

迪杰斯特拉算法是一种用于求解带权有向图中单源最短路径的算法。它以一个起始节点为基准，逐步扩展到其他节点，通过不断更新节点的最短路径来找到起始节点到其他节点的最短路径。

算法的基本思想是从起始节点开始，先将起始节点到所有其他节点的距离初始化为无穷大，然后逐步更新距离，直到找到最短路径。具体步骤如下：

1. 初始化距离数组dist[]，表示起始节点到各个节点的最短距离。将起始节点的距离初始化为0，其他节点的距离初始化为无穷大。

2. 创建一个集合visited[]，用于记录已经求得最短路径的节点。

3. 重复以下步骤，直到所有节点都被访问过：
a. 从未访问过的节点中选择一个距离起始节点最近的节点，将其标记为visited[]。
b. 更新与该节点相邻的节点的最短距离。如果经过当前节点到达相邻节点的路径比原先的最短距离更短，则更新最短距离。

4. 最终，dist[]数组中存储的就是起始节点到各个节点的最短路径长度。

迪杰斯特拉算法的时间复杂度为O(V^2)，其中V为节点数。该算法适用于边的权重非负的情况。如果希望在存在负权边的图中求解最短路径，则需要使用其他算法，如贝尔曼-福特算法或弗洛伊德算法。