$\Huge\color{orchid}{点击此处获取更多干货}$

Dijkstra算法（优先队列）

本篇首先根据上一次原理和简单实现的介绍，提出两个可能的疑点：
1. 邻接矩阵存储，无论是节点数过多还是图的稀疏度过大，都会导致算法时空复杂度爆炸式增长，用邻接表能不能优化它？
2. 每一轮寻找距离起点最近的节点时用的是枚举，有没有更快的寻找方式？

从算法最主要的松弛操作中看，选择距离起点最近的节点，显然是有更好的方法，用STL中的优先队列（priority_queue）既可以取得最小值，也可以在对数级时间下自动排序，比枚举的线性时间更快。另外，既然是“更新后继节点的距离”，那么只需要靠邻接表取得后继节点的信息即可，不需要像邻接矩阵那样存储很多无效信息，而且也不涉及两个节点间有没有边的判断，所以邻接表在此处可以平替掉邻接矩阵，如此实现之下，时间复杂度可减少到$O((n+m)log_2m)$，小于简单实现中的$O(n^2+m)$，其中对数项来自priority_queue容器底层的二叉堆

C++ 代码

ALGraph类来自前置知识

vector<int> ALGraph::shortestDistance(int s) {
    vector<int> dists(numVex + 1, 1e9 + 7), visit(numVex + 1, 0);
    //priority_queue默认大根堆，模板参数在此特别展开介绍
    priority_queue<
        pair<int, int>,             //元素类型，对组的实际含义为{距离，节点}
        vector<pair<int, int>>,     //底层实现容器（默认vector）
        greater<pair<int, int>>     //谓词（默认less），后两个参数要么都指定，要么都默认
    > q;
    dists[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        auto& node = q.top();//堆顶是末位元素，对应未访问节点中距离起点最近的节点
        q.pop();
        int cur = node.second, dist = node.first;
        if (visit[cur]) {
            continue;
        }
        visit[cur] = 1;//访问它
        //遍历后继节点，执行松弛
        for (auto& ed : adjList[cur]) {
            if (dists[ed.nxt] > dist + ed.val) {
                dists[ed.nxt] = dist + ed.val;
                q.push({dists[ed.nxt], ed.nxt});
            }
        }
    }
    return dists;
}