Dijkstra算法的原理

Dijkstra算法的原理可以清晰地分为以下几个步骤和要点：

1. 初始化：
   • 引入一个辅助数组D，其中D[i]表示从起始点（源点）到顶点i的当前已知最短距离。如果起始点与顶点i之间没有直接连接，则D[i]被初始化为无穷大（∞）。
   • 引入两个集合S和U，S集合包含已找到最短路径的顶点及其距离，初始时只包含起始点，其距离设为0（即D[起始点] = 0）；U集合包含未找到最短路径的顶点及其到起始点的距离。
2. 选择机制：
   • 从U集合中选择距离起始点最近的顶点k，将其加入到S集合中，并从U集合中删除。这一步保证了我们始终先处理距离起始点最近的顶点。
3. 更新机制（松弛操作）：
   • 对于U集合中的每一个顶点i，检查是否存在一条从起始点经过顶点k到顶点i的路径，其长度小于D[i]。如果存在，则更新D[i]为这个更短的距离，并更新顶点i的父节点为k。这一步是算法的核心，通过不断更新最短距离来找到从起始点到各个顶点的最短路径。
4. 迭代过程：
   • 重复执行选择机制和更新机制，直到U集合为空，即所有顶点都已被处理过。此时，D数组中存储的就是从起始点到各个顶点的最短距离。
5. 算法特点：
   • Dijkstra算法是一个单源最短路径算法，即只能找到从单个起始点到其他所有顶点的最短路径。
   • 算法要求图中不存在负权边，因为负权边可能导致算法陷入无限循环或得到错误的结果。
6. 贪心策略：
   • Dijkstra算法采用贪心策略，每次总是选择当前距离起始点最近的顶点进行处理，这种策略保证了算法能够逐步逼近最短路径。
7. 时间复杂度：
   • 如果使用邻接矩阵存储图，则Dijkstra算法的时间复杂度为O(n^2)，其中n为顶点的数量。如果使用邻接表存储图并结合最小堆优化，则时间复杂度可以降低到O((m+n)log n)，其中m为边的数量，n为顶点的数量。

归纳起来，Dijkstra算法通过初始化、选择机制、更新机制和迭代过程等步骤，采用贪心策略逐步找到从起始点到各个顶点的最短路径，是解决有权图中最短路径问题的有效算法。