Dijkstra 算法贪心思想

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法。它通过不断选择当前最优的节点来逐步确定从源节点到其他节点的最短路径。

算法的基本思想是，维护一个距离数组，记录源节点到其他节点的当前最短距离。初始时，源节点距离为0，其他节点距离为无穷大。然后，从未标记的节点中选择一个离源节点最近的节点，将其标记为已访问，并更新与该节点相邻的节点的距离值。

具体步骤如下：
1. 创建一个距离数组，用于记录源节点到其他节点的当前最短距离。
2. 将距离数组初始化为无穷大，源节点的距离初始化为0。
3. 选择距离数组中未被标记的节点中，距离源节点最近的节点，将其标记为已访问。
4. 更新与该节点相邻的节点的距离值，如果通过当前选中的节点到达相邻节点的距离小于距离数组中记录的值，则更新距离数组中的值。
5. 重复步骤3和4，直到所有节点都被标记为已访问。

通过这种贪心策略，Dijkstra算法可以保证每次选择的节点都是当前最优的，从而逐步确定从源节点到其他节点的最短路径。该算法的时间复杂度为O(V^2)，其中V是节点的数量。