贪心算法单源最短路径

贪心算法可以用于解决单源最短路径问题，其中 Dijkstra 算法就是一种经典的贪心算法。

Dijkstra 算法的基本思路是：从起点开始，维护一个到每个点的最短距离，每次找到当前未确定最短路径的点中距离起点最近的点，然后更新其周围点的最短路径。具体来说，算法的过程如下：

1. 初始化起点到自身的距离为 0，其余点到起点的距离为无穷大。

2. 维护一个集合 S，其中包含所有已确定最短路径的点。

3. 在未确定最短路径的点中，找到距离起点最近的点 v，将其加入集合 S 中。

4. 对于 v 的每个邻接点 w，更新起点到 w 的距离。如果起点到 w 的距离变小了，就更新其最短距离。

5. 重复步骤 3 和 4，直到所有点都被加入集合 S。

6. 最终得到起点到所有点的最短距离。

Dijkstra 算法的时间复杂度为 O(n^2)，其中 n 是节点数。可以通过使用堆等数据结构来优化算法，将时间复杂度降为 O(mlogn)，其中 m 是边数。