Dijkstra单源最短路

过程动画

代码实现

int g[N][N], dist[N];
bool visited[N];
int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));  //把起点到所有点的距离都初始化为大数0x3f
    dist[1] = 0; //起点到自己的最短距离是0
    
    //外层循环(每次把一个点加入已访问点集)
    for(int i = 1; i <= n; i++)   
    {
        int t = -1;
        
        //内层循环1(找到离当前已访问点集V最近的点，加入V中)
        for(int j = 1; j <= n; j++)  
        {
            if(!visited[j] && (t == -1 || dist[j] < dist[t]))  //"<"隐含地排除了所有与已访问点集暂无边连接(dist[j]=0x3f)的点
                t = j;
        }
        visited[t] = true;
        
        //内层循环2(更新最短距离dist数组)
        for(int j = 1; j <= n; j++)  
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

2.时间复杂度

---

由代码实现可以清晰地看到一共有2层for循环(其中第二层循环包括2个循环)，所以复杂度为\(\Theta(n^2)\)

3.条件

---

不能存在负权边

4.堆优化的思想（更适用于稀疏图）

---

1）基本思想

用 最小堆 来保持集合Y中的顶点，使Y组中离V-Y最近的顶点y可以在 O(log n) 时间内被选出

与每个顶点v相关的键就是它的标记λ[v].

想象你在玩一个寻宝游戏，城市是图中的节点，道路是边，你需要找到从起点到每个城市的最短路径：

2）普通Dijkstra算法（数组实现）

1. 你有一个记事本，上面写着每个城市到起点的当前已知最短距离
2. 每次你都要浏览整个记事本，找出未访问城市中距离最小的那个
3. 对于大城市网络，这个查找过程非常耗时（O(V)时间）

3）堆优化的Dijkstra算法

1. 你用一个特殊的”智能记事本”（最小堆）来存储城市和它们的距离
2. 这个”智能记事本”有神奇的能力：它总是把当前距离最小的城市放在第一页
3. 你只需要看第一页就能立刻知道下一个要访问的城市（O(log V)时间）
4. 当你更新某个城市的距离时，”智能记事本”会自动重新排序（也是O(log V)时间）

4）为什么堆优化更快？

1. 快速找到最小值：普通方法需要查看所有未访问的城市，而堆总是把最小的放在顶部
2. 高效更新：当发现更短路径时，堆能高效地调整元素位置

5）实际过程简化说明：

1. 将起点放入堆中，距离为0
2. 不断从堆顶取出当前距离最小的顶点
3. 考察这个顶点的所有邻居，如果通过这个顶点可以得到更短的路径，则更新邻居的距离并调整堆
4. 重复步骤2-3直到堆为空

6）时间复杂度

通过堆优化，Dijkstra算法的时间复杂度从\(\Theta(V²)\)降低到了\(\Theta(E log V)\)，这对于边数远小于顶点数平方的稀疏图来说是巨大的提升。

5.堆优化代码

---

// 初始化
1. Y ← V - {1};
   λ[1] ← 0;
   key(1) ← λ[1]

// 处理与起点相邻的顶点
2. for y ← 2 to n
3.    if y is adjacent to 1 then
4.       λ[y] ← length[1, y]
5.       key(y) ← λ[y]
6.       insert(H, y)
7.    else
8.       λ[y] ← ∞
9.       key(y) ← λ[y]
10.   end if
11. end for

// 主循环
12. for j ← 1 to n - 1
13.    y ← deletemin(H)
14.    Y ← Y - {y}  // 从未处理集合中删除顶点y
15.    for each vertex w ∈ Y that is adjacent to y
16.       if λ[y] + length[y, w] < λ[w] then
17.          λ[w] ← λ[y] + length[y, w]
18.          key(w) ← λ[w]
19.       end if
20.       if w ∉ H then 
21.          insert(H, w)
22.       else 
23.          siftup(H, H⁻¹(w))
24.       end if
25.    end for
26. end for

堆（Heap）的基本操作（插入、删除、更新）的时间复杂度都是 O(log n)

其中 n 是堆中元素的数量。这是因为这些操作都需要调整堆的结构，而调整的过程与堆的高度成正比，而堆的高度是 log n。

• 堆插入操作：新元素首先被添加到堆的末尾，然后通过”上浮”（sift-up）操作调整其位置，直到满足堆的性质。在最坏情况下，新元素需要从最底层上浮到根节点，这需要 O(log n) 的时间。
• 堆删除操作（通常是删除堆顶元素）：堆顶元素被移除后，通常用堆的最后一个元素替代它，然后通过”下沉”（sift-down）操作调整堆顶元素的位置。在最坏情况下，这个元素需要从根节点下沉到最底层，这也需要 O(log n) 的时间。
• 堆更新操作：更新堆中的某个元素后，可能需要进行上浮或下沉操作来维护堆的性质，具体取决于更新是增加了元素的值还是减小了元素的值。无论哪种情况，调整的时间复杂度都是 O(log n)。

堆优化版Dijkstra算法的时间复杂度主要来自几个关键操作：

1）初始化阶段（行1-11）：

• 对每个顶点进行初始化：O(V)
• 对于每个与起点相邻的顶点，将其插入堆中：每次插入操作为O(log V)
• 最坏情况下，所有顶点都与起点相邻，总共需要O(V log V)

2）主循环（行12-24）：

• 主循环执行n-1次（即V-1次）
• 每次循环中：
  • 从堆中删除最小元素（deletemin）：O(log V)
  • 对于被删除顶点的每个邻接顶点，需要更新其距离并调整堆（sift）：O(log V)

3）边的处理：

• 算法中每条边最多被处理一次
• 每次处理一条边时需要进行堆操作：O(log V)
• 所有边的处理总复杂度为：O(E log V)

综合以上分析：
1) 初始化阶段：O(V log V)
2) 主循环中的deletemin操作：执行V-1次，总复杂度为O(V log V)
3) 边的处理：总复杂度为O(E log V)

总时间复杂度为：O(V log V + E log V) = O((V+E) logV) = O(E logV)

上述分析是针对”稀疏图”的时间复杂度，若对”稠密图”使用堆优化的算法，则时间复杂度为O(m/ε)

对比普通的Dijkstra算法（复杂度为O(V²)），堆优化版本在处理稀疏图（即E远小于V²）时具有显著优势

6.正确性证明

---

7.对比Floyd

---

• Dijkstra只可以求出任意点到达源点的最短距离，Floyd可以求出任意两点间的最短距离
• Dijkstra算法的思想是贪心，Floyd算法的思想是动态规划
• Dijkstra时间复杂度为
  \(O(n^2)\)
  Floyd算法时间复杂度为
  \(O(n^3)\)

8.对比Prim

---

我的直觉是，Dijkstra算法和最小生成树的Prim算法有很多相似之处：

1. 都从一个起始点开始，逐步扩展
2. 都使用优先队列或最小堆来选择下一步
3. 都使用贪心策略，每一步都选择当前最优解
4. 都维护一个已访问集合和一个未访问集合

不过其区别在于：

1. 目标不同：Prim算法求最小生成树(MST)，Dijkstra算法求单源最短路径
2. 维护的距离含义不同：Prim维护的是到已有树的最小距离，Dijkstra维护的是到源点的最短路径
3. 结果不同：Prim产生的是一棵树，Dijkstra产生的是一个以源点为根的最短路径树

这两个算法之所以如此相似，是因为它们本质上都是解决图上的优化问题，并且都采用了类似的贪心思想。实际上，这两个算法可以被看作是同一个一般框架的特例，这个框架就是所谓的”边缘松弛”(edge relaxation)技术。