Dijkstra算法求最短路径

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法。它的基本思想是从起点开始，逐步扩展到其他节点，每次选择当前距离起点最近的一个节点进行扩展，直到扩展到终点或者所有节点都被扩展完毕。在扩展的过程中，维护一个距离数组，记录起点到每个节点的最短距离，同时维护一个集合，记录已经确定最短路径的节点。每次扩展一个节点时，更新与该节点相邻的节点的距离，并将其加入集合中。重复这个过程，直到终点被加入集合或者集合为空。

Dijkstra算法的时间复杂度为O(n^2)，其中n为节点数。如果使用堆优化的Dijkstra算法，时间复杂度可以降为O(mlogn)，其中m为边数。在实际应用中，稠密图一般使用朴素版Dijkstra算法，稀疏图则使用堆优化版Dijkstra算法。