图的单源最短路径：Dijkstra算法

描述
Dijkstra算法用于解决带权有向图或无向图的单源最短路径问题，要求所有边的权重非负。该算法通过贪心策略逐步确定从源点到其他各顶点的最短路径，适用于网络路由、地图导航等场景。

解题过程

1. 基本思想

   • 将顶点分为两类：已确定最短路径的顶点集合（S）、未确定的顶点集合（U）。
   • 初始化时，S仅包含源点，U包含其他顶点。源点到自身的距离为0，到其他顶点的距离初始化为无穷大（表示暂不可达）。
   • 每次从U中选出距离源点最近的顶点，加入S，并更新该顶点邻居到源点的距离（松弛操作）。
   • 重复此过程直至所有顶点均加入S。

2. 算法步骤
   步骤1：初始化

   • 创建距离数组dist[]，dist[src] = 0，其余设为∞。
   • 创建集合S（初始为空）和优先队列（最小堆）U，存储所有顶点及其当前距离。

   步骤2：选择当前最短路径顶点

   • 从U中取出距离最小的顶点u（即当前离源点最近的未处理顶点），将其加入S。
   • 若U为空，算法结束。

   步骤3：松弛操作

   • 遍历u的所有邻居v，若通过u到v的路径比已知路径更短，则更新dist[v]：

     如果 dist[u] + weight(u, v) < dist[v]:
         dist[v] = dist[u] + weight(u, v)
     

   • 更新后，调整U中v的距离（若使用堆，需动态调整优先级）。

   步骤4：重复

   • 重复步骤2和3，直至U为空。

3. 示例演示
   以有向图为例（顶点A、B、C、D，源点为A）：

   • 边权重：A→B=4, A→C=2, B→D=3, C→B=1, C→D=5
   • 初始化：dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞
   • 迭代1：选A（距离0），更新邻居B=4、C=2。
   • 迭代2：选C（距离2），更新B=min(4, 2+1)=3、D=2+5=7。
   • 迭代3：选B（距离3），更新D=min(7, 3+3)=6。
   • 迭代4：选D（距离6），结束。
     最终最短路径：A→B=3, A→C=2, A→D=6。

4. 时间复杂度与优化

   • 使用数组遍历选择最小顶点：O(V²)，适合稠密图。
   • 使用最小堆（优先队列）：O((V+E)logV)，适合稀疏图。
   • 注意：若存在负权边，Dijkstra算法可能失效（需改用Bellman-Ford算法）。

5. 关键点总结

   • 贪心策略：每次选择当前最短路径顶点，局部最优保证全局最优。
   • 非负权约束：确保已确定的顶点距离不再被更新。
   • 松弛操作的核心：通过中间顶点缩短路径距离。