别再死记硬背Dijkstra了！用C++邻接表+优先队列实现最短路径（附LeetCode实战）

在算法面试和工程实践中，Dijkstra算法是解决单源最短路径问题的经典选择。但很多开发者仍停留在邻接矩阵+暴力搜索的传统实现上，面对LeetCode等平台的大规模图数据时，往往遭遇性能瓶颈。本文将带你突破这一困境，掌握 邻接表存储 与 优先队列优化 的现代实现方案，并手把手解决LeetCode 743「网络延迟时间」问题。

1. 为什么需要优化传统Dijkstra实现？

1.1 邻接矩阵的局限性

邻接矩阵虽然直观，但在稀疏图中会浪费大量空间。例如处理10万个节点的社交网络图时：

存储方式	空间复杂度	10万节点所需空间
邻接矩阵	O(V²)	40GB
邻接表	O(V+E)	约10MB

// 邻接矩阵声明示例（不推荐）
vector<vector<int>> graph(V, vector<int>(V, INF));

1.2 暴力搜索的性能瓶颈

传统实现通过遍历所有节点寻找最小距离节点，导致O(V²)时间复杂度。当V超过1万时，算法响应时间将呈指数级增长：

// 低效的最小距离查找（典型面试错误写法）
int minDist = INF, u = -1;
for(int v = 0; v < V; ++v) {
    if(!visited[v] && dist[v] < minDist) {
        minDist = dist[v];
        u = v;
    }
}

2. 现代Dijkstra实现核心技术

2.1 邻接表存储优化

邻接表使用vector+pair的组合，完美适配稀疏图场景：

// 推荐邻接表声明方式
vector<vector<pair<int, int>>> adj(V); // adj[u] = { (v1, w1), (v2, w2)... }

// 添加边操作（有向图示例）
void addEdge(int u, int v, int w) {
    adj[u].emplace_back(v, w);
}

2.2 优先队列加速

使用STL的priority_queue将查找最小距离节点的复杂度从O(V)降至O(logV)：

// 最小堆定义（存储距离和节点）
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

// 初始化优先队列
pq.emplace(0, src);
dist[src] = 0;

注意：默认的priority_queue是最大堆，需通过 greater<> 转换为最小堆

3. 完整工程级实现模板

3.1 核心算法框架

vector<int> dijkstra(int src, const vector<vector<pair<int, int>>>& adj) {
    const int V = adj.size();
    vector<int> dist(V, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    dist[src] = 0;
    pq.emplace(0, src);
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 重要优化：跳过旧数据
        
        for (const auto& [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

3.2 关键优化点解析

1. 延迟删除技术 ：通过 if(d > dist[u]) continue 避免堆中数据重复处理
2. 智能指针传递 ：使用 const auto& 避免不必要的拷贝
3. 结构化绑定 ：C++17的 auto [d, u] 语法提升代码可读性

4. LeetCode 743「网络延迟时间」实战

4.1 问题重述

给定有向加权图和源节点，计算信号传播到所有节点的最短时间。如果不能使所有节点收到信号，返回-1。

4.2 完整AC代码

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // 构建邻接表
        vector<vector<pair<int, int>>> adj(n+1);
        for(const auto& t : times) {
            adj[t[0]].emplace_back(t[1], t[2]);
        }
        
        // Dijkstra算法
        vector<int> dist(n+1, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        
        dist[k] = 0;
        pq.emplace(0, k);
        
        while(!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if(d > dist[u]) continue;
            
            for(const auto& [v, w] : adj[u]) {
                if(dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        
        // 计算结果
        int max_time = *max_element(dist.begin()+1, dist.end());
        return max_time == INT_MAX ? -1 : max_time;
    }
};

4.3 复杂度分析

操作	时间复杂度	空间复杂度
构建邻接表	O(E)	O(V+E)
优先队列处理	O(E logV)	O(V)
结果计算	O(V)	O(1)

5. 常见陷阱与调试技巧

5.1 易错点排查表

错误现象	可能原因	解决方案
结果比预期大	未初始化dist为INF	检查vector初始化值
部分节点距离错误	有向图/无向图处理错误	确认边的添加方式
堆溢出或超时	未处理重复节点	添加 if(d > dist[u]) continue
返回-1但应可达	节点编号从0/1开始不一致	统一节点编号体系

5.2 调试建议

1. 打印邻接表确认图构建正确

for(int u=1; u<=n; ++u) {
    cout << u << ": ";
    for(auto [v,w] : adj[u]) 
        cout << "(" << v << "," << w << ") ";
    cout << endl;
}

2. 在优先队列操作后打印dist数组
3. 使用小规模测试用例验证边界条件