手写Dijkstra单源最短路径算法

题目描述：
Dijkstra算法是解决单源最短路径问题的经典算法，用于计算从一个源点到图中所有其他顶点的最短路径。它要求图中边的权重非负。请手写实现Dijkstra算法，并分析其时间复杂度和适用场景。

解题过程：

1. 算法核心思想
Dijkstra算法采用贪心策略，每次从未确定最短路径的顶点中选取距离源点最近的顶点，然后通过该顶点松弛（更新）其邻接顶点的距离。最终得到从源点到所有顶点的最短距离。

2. 算法步骤拆解
假设图有 \(n\) 个顶点，源点为 \(s\)，图的表示方式为邻接表。

1. 初始化

   • 创建距离数组 dist[]，dist[i] 表示源点 \(s\) 到顶点 \(i\) 的当前最短距离估计。初始时，dist[s] = 0，其他顶点为无穷大（代码中可用一个大数如 INT_MAX 表示）。
   • 创建一个集合（或数组）用于记录哪些顶点的最短距离已确定，初始时都未确定。
   • 通常使用优先队列（最小堆） 来高效选取当前距离最小的未确定顶点。

2. 主循环
   当还有未确定最短距离的顶点时：

   • 从优先队列中取出当前距离最小的顶点 \(u\)（即未确定顶点中 dist[u] 最小的）。
   • 将 \(u\) 标记为“已确定”（因为其 dist[u] 此时已是最短距离）。
   • 对 \(u\) 的每个邻接顶点 \(v\)，执行松弛操作：
     如果 dist[u] + weight(u, v) < dist[v]，则更新 dist[v] = dist[u] + weight(u, v)，并将 \(v\) 加入优先队列（或更新其在队列中的距离）。

3. 结束
   当优先队列为空时，dist[] 中存储的即为从源点 \(s\) 到所有顶点的最短距离。

3. 关键细节说明

• 为什么需要优先队列：如果不使用优先队列，每次需遍历所有未确定顶点找最小距离，时间复杂度为 \(O(V^2)\)。使用优先队列（最小堆）可将找最小距离的操作降至 \(O(\log V)\)，整体复杂度优化为 \(O((V+E)\log V)\)。
• 为什么边权必须非负：如果存在负权边，已确定的顶点可能通过负权边获得更短距离，违反贪心选择性质，导致结果错误。
• 松弛操作的意义：通过新确定的顶点“中转”，尝试缩短其他顶点的距离估计。

4. 手写实现（C++示例）

#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> PII; // (距离, 顶点)

void dijkstra(int s, vector<vector<PII>>& graph, vector<int>& dist) {
    int n = graph.size();
    dist.assign(n, INT_MAX);
    dist[s] = 0;
    
    // 最小堆，按距离从小到大排列
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, s});
    
    while (!pq.empty()) {
        int d = pq.top().first;  // 当前距离
        int u = pq.top().second; // 当前顶点
        pq.pop();
        
        // 如果取出的距离大于当前记录的距离，说明是旧数据，跳过
        if (d > dist[u]) continue;
        
        // 遍历邻接点
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second; // u->v 的边权
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

5. 算法分析

• 时间复杂度：
  每个顶点和每条边最多被处理一次。优先队列的插入和删除操作均为 \(O(\log V)\)，因此总复杂度为 \(O((V+E)\log V)\)。在稠密图（\(E \approx V^2\)）中约为 \(O(V^2 \log V)\)，但使用斐波那契堆可进一步优化到 \(O(V \log V + E)\)。
• 空间复杂度：
  \(O(V+E)\) 用于存储图和距离数组，优先队列最多存储 \(O(V)\) 个顶点。

6. 应用场景

• 网络路由协议（如OSPF）
• 地图导航软件的最短路径计算
• 社交网络中“最短关系链”查找
• 任何需要非负权图单源最短路径的场景

7. 常见变体与面试考点

• 如何输出最短路径而不仅是距离？——记录前驱节点。
• 如果只需要到特定终点的最短路径，可在取出终点时提前结束。
• 边权相等时，退化为BFS。
• 对比其他最短路径算法：Bellman-Ford（可处理负权，\(O(VE)\)），Floyd-Warshall（多源，\(O(V^3)\)）。

总结：Dijkstra算法的核心是贪心选择 + 松弛操作，通过优先队列优化效率。实现时需注意优先队列中可能存有旧数据，需用 d > dist[u] 判断跳过。掌握其原理和实现是图算法面试的重要基础。