图论中的最短路径问题（Dijkstra算法）

题目描述
给定一个带权有向图（或无向图），图中每条边的权重为非负值，求从一个源点（如顶点 \(s\)）到图中所有其他顶点的最短路径长度。

解题过程

1. 核心思想
Dijkstra算法通过贪心策略逐步确定离源点最近的顶点，并利用这些顶点的最短路径来更新相邻顶点的距离。算法维护一个集合 \(S\)，表示已确定最短路径的顶点，初始时 \(S\) 为空。

2. 初始化

• 创建一个距离数组 \(dist\)，其中 \(dist[s] = 0\)，表示源点到自身的距离为0；其他顶点的距离初始化为无穷大（\(\infty\)）。
• 创建一个优先队列（最小堆）\(Q\)，存储所有未确定最短路径的顶点，以 \(dist\) 值作为优先级。初始时所有顶点都在 \(Q\) 中。

3. 迭代过程
重复以下步骤直到 \(Q\) 为空：

1. 选择当前距离最小的顶点：从 \(Q\) 中取出 \(dist\) 值最小的顶点 \(u\)（即当前离源点最近的未处理顶点）。
2. 标记已确定：将 \(u\) 加入集合 \(S\)，表示 \(u\) 的最短路径已确定。
3. 松弛操作：遍历 \(u\) 的所有邻居顶点 \(v\)，若通过 \(u\) 到 \(v\) 的路径比当前已知路径更短，则更新 \(dist[v]\)：

\[ dist[v] = \min(dist[v], dist[u] + w(u, v)) \]

其中 \(w(u, v)\) 是边 \((u, v)\) 的权重。若 \(dist[v]\) 被更新，则调整 \(v\) 在优先队列中的位置。

4. 细节说明

• 贪心正确性：由于所有边权非负，当前从 \(Q\) 中取出的最小 \(dist\) 顶点，其距离不可能再被其他路径更新，因此可标记为已确定。
• 时间复杂度：
  • 使用二叉堆实现优先队列时，每次提取最小值和调整优先级需 \(O(\log V)\)，总复杂度为 \(O((V+E)\log V)\)。
  • 若使用数组遍历寻找最小值，复杂度为 \(O(V^2)\)，适合稠密图。

5. 示例演示
以以下图为例（边权非负）：

顶点：A, B, C, D  
边：A→B(1), A→C(4), B→C(2), B→D(5), C→D(1)  
源点：A  

• 初始化：\(dist[A]=0\), 其他为 \(\infty\)。
• 第一轮：取出 \(A\)，更新邻居 \(B=1\), \(C=4\)。
• 第二轮：取出 \(B\)，更新 \(C=\min(4, 1+2)=3\), \(D=1+5=6\)。
• 第三轮：取出 \(C\)，更新 \(D=\min(6, 3+1)=4\)。
• 结果：\(dist[A]=0, B=1, C=3, D=4\)。

6. 关键限制
Dijkstra算法不能处理负权边，因为负权可能使已确定的“最短路径”被推翻，破坏贪心正确性。若需处理负权，应使用Bellman-Ford算法。

通过以上步骤，Dijkstra算法可高效求解非负权图中的单源最短路径问题。