Dijkstra算法（单源最短路径）

Dijkstra算法是解决非负权图单源最短路径问题的经典算法。它能够找到从源点到图中所有其他顶点的最短路径。下面我们分步骤详细讲解。

1. 问题描述

给定一个带权有向图（或无向图），图中每条边的权值均为非负数，以及一个源点（起点）。要求找出从源点到图中所有其他顶点的最短路径长度（即最短距离）。

2. 核心思想

Dijkstra算法采用贪心策略。它维护一个集合S，该集合包含已经找到最短路径的顶点。算法反复从未确定最短路径的顶点集合中，选取一个距离源点最近的顶点，将其加入S，并松弛（更新）其所有邻接顶点的距离估计值。这个过程直到所有顶点都加入S为止。

“松弛”操作是算法的关键：对于一条边(u, v)，如果通过顶点u去往v的路径比当前已知的到v的最短路径更短，则更新v的最短距离估计值。

3. 算法步骤详解

我们通过一个具体例子来理解。假设有下图，源点为顶点0。边上的数字表示权重。

       (1)
    4 /   \ 2
     /     \
    (0)---(2)
        1

步骤1：初始化

• 创建一个数组dist，用于记录从源点（0）到每个顶点的当前最短距离估计值。
  • dist[0] = 0 （源点到自己的距离为0）
  • 对于其他所有顶点v（v ≠ 0），dist[v] = ∞ （初始时认为距离为无穷大）
• 创建一个集合S（或一个标记数组visited），用于记录哪些顶点已经确定了最短路径。初始时，S为空。

初始状态：

顶点:   0   1   2
dist:   0   ∞   ∞
S:      {}

步骤2：选择当前距离源点最近的未访问顶点

• 当前所有顶点中，dist值最小且不在S中的顶点是顶点0（dist[0] = 0）。
• 将顶点0加入集合S，表示顶点0的最短路径已确定。

当前状态：

S: {0}

步骤3：松弛操作

• 检查顶点0的所有邻接顶点（即顶点1和顶点2）。
• 对于邻接顶点v，计算新的距离：dist[0] + weight(0, v)。
  • 顶点1：0 + 4 = 4。因为4 < ∞，所以更新dist[1] = 4。
  • 顶点2：0 + 1 = 1。因为1 < ∞，所以更新dist[2] = 1。

更新后状态：

顶点:   0   1   2
dist:   0   4   1
S:      {0}

步骤4：重复步骤2和3

• 第二轮：在未访问顶点（顶点1和2）中，选择dist值最小的顶点，即顶点2（dist[2] = 1）。
• 将顶点2加入S。
• 松弛顶点2的邻接顶点（顶点0和顶点1）。顶点0已在S中，忽略。
  • 顶点1：通过顶点2的新路径长度为 dist[2] + weight(2, 1) = 1 + 2 = 3。因为3 < 4，所以更新dist[1] = 3。

更新后状态：

顶点:   0   1   2
dist:   0   3   1
S:      {0, 2}

• 第三轮：在未访问顶点（只剩顶点1）中，选择dist值最小的顶点，即顶点1（dist[1] = 3）。
• 将顶点1加入S。
• 松弛顶点1的邻接顶点（顶点0和顶点2）。它们都已确定最短路径（在S中），无需更新。

最终状态：

顶点:   0   1   2
dist:   0   3   1
S:      {0, 1, 2}

步骤5：算法结束
所有顶点都已加入集合S，算法终止。dist数组中存储的就是从源点0到各个顶点的最短距离。

4. 数据结构与优化

上述过程需要频繁进行两个操作：

1. 查找未访问顶点中dist值最小的顶点。
2. 更新某个邻接顶点的dist值。

如果使用简单的数组遍历来实现步骤2，时间复杂度为O(V²)（V为顶点数）。对于稀疏图（边数E远小于V²），这效率不高。

优化：使用优先队列（最小堆）

• 将未确定最短路径的顶点及其当前的dist值放入一个最小堆中。堆顶元素始终是dist值最小的顶点。
• 查找最小顶点的操作变为O(1)（查看堆顶）。
• 删除堆顶和更新某个顶点的dist值（即减少某个键的值，在堆中需要上浮调整）的时间复杂度为O(log V)。
• 总时间复杂度可优化至O((V+E) log V)，这在稀疏图中非常有利。

5. 算法特性总结

• 适用条件：图中所有边的权重必须为非负值。负权边会导致贪心选择失效。
• 时间复杂度：
  • 朴素实现（使用数组）：O(V²)
  • 优化实现（使用二叉堆优先队列）：O((V+E) log V)
• 空间复杂度：O(V)（用于存储dist数组、visited标记和优先队列）。

通过以上步骤，Dijkstra算法系统地、一步步地确定了从单一源点到所有其他顶点的最短路径，其核心在于贪心策略和松弛操作。