手写Dijkstra单源最短路径算法

题目描述
给定一个带权有向图（或无向图）、一个起点 src，要求找出从 src 到图中所有其他顶点的最短路径长度（即最短距离）。图中边的权重均为非负值。你需要手写实现 Dijkstra 算法，并分析其时间与空间复杂度。

解题过程

Dijkstra 算法是一种贪心算法，用于求解非负权图的单源最短路径。它的核心思想是：每次从未确定最短距离的顶点中，选取当前距离起点最近的顶点，然后通过该顶点更新其相邻顶点的距离。

1. 算法步骤拆解

假设图有 n 个顶点，编号从 0 到 n-1，图的表示可以采用邻接表（节省空间，适合稀疏图）或邻接矩阵。这里以邻接表为例。

输入：

• 顶点数 n，边列表（每个边包含 (u, v, w)，表示从 u 到 v 的权重为 w）
• 起点 src

输出：

• 一个数组 dist[]，dist[i] 表示 src 到顶点 i 的最短距离。如果不可达，则记为 INF（一个很大的数，如 INT_MAX）。

步骤：

1. 初始化：

   • dist[src] = 0，其他 dist[i] = INF。
   • 使用一个优先队列（小顶堆）存储 (距离, 顶点)，初始将 (0, src) 入队。
   • 使用一个集合（或布尔数组）visited 记录哪些顶点的最短距离已确定（可选，见优化说明）。

2. 循环直到优先队列为空：
   a. 弹出堆顶 (d, u)，如果 d > dist[u]，说明这是旧数据（已更新过更短距离），跳过（lazy deletion）。
   b. 否则，此时 dist[u] 已是最短距离，可以标记 visited[u] = true（如果使用 visited 数组，则可在弹出时检查是否已访问，是则跳过）。
   c. 遍历 u 的所有邻接边 (u, v, w)：
   如果 dist[u] + w < dist[v]，更新 dist[v] = dist[u] + w，并将 (dist[v], v) 入队。

3. 返回 dist 数组。

2. 代码实现（C++示例）

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

vector<int> dijkstra(int n, vector<vector<pair<int, int>>>& graph, int src) {
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    dist[src] = 0;
    
    // 小顶堆：pair<距离, 顶点>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        // 如果当前弹出的距离大于已记录的最短距离，跳过（lazy deletion）
        if (d > dist[u]) continue;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

如何使用：
先构建邻接表 graph，graph[u] 是一个列表，每个元素是 (v, w) 表示从 u 到 v 的边权重为 w。

3. 复杂度分析

• 时间复杂度：
  每个顶点最多入队一次，出队一次，每次出队后遍历其所有邻接边。设顶点数 V，边数 E。
  优先队列的 push/pop 操作是 O(log V)，因此总复杂度为 O((V + E) log V)。在稀疏图中近似 O(E log V)。

• 空间复杂度：
  O(V + E) 用于存储图，O(V) 用于 dist 数组和优先队列。

4. 关键点与注意事项

1. 非负权重限制：
   Dijkstra 算法要求所有边权重非负。如果存在负权边，应使用 Bellman-Ford 算法。

2. 为什么使用优先队列：
   优先队列能快速取出当前未确定顶点中距离最小的，这是 Dijkstra 贪心选择的关键。

3. Lazy Deletion 技巧：
   在优先队列中，同一个顶点可能被多次 push（距离更新时）。弹出时如果发现该距离不是最新最短距离，则跳过，避免重复处理。

4. 有向图与无向图：
   无向图只需将每条边存为两条有向边即可。

5. 路径记录：
   如果需要输出具体路径，可额外维护 prev[] 数组，在更新 dist[v] 时记录 prev[v] = u，最后从终点回溯。

扩展思考

• 如果图很稠密（E ≈ V^2），使用邻接矩阵 + 未使用优先队列的朴素 Dijkstra（O(V^2)）可能更优。
• 在边权均为 1 的特殊情况下，可直接用 BFS（O(V+E)）。
• Dijkstra 不能处理负权边，因为贪心选择当前最短距离顶点后，无法保证后续不会通过负权边得到更短距离。

通过以上步骤，你应该能够理解 Dijkstra 算法的原理、实现与细节，并能应对相关面试问题。