dijkstra堆优化c++

### Dijkstra算法堆优化C++实现

#### 使用优先队列优化Dijkstra算法的时间复杂度

为了提高效率，可以利用最小堆来存储待处理节点及其当前距离估计值。这样每次都能快速取出具有最小临时距离的节点进行扩展操作[^2]。

#### 数据结构的选择

采用`pair<int, int>`类型的元素存入标准库中的`priority_queue`容器内，其中第一个分量代表权值而第二个则是结点编号；由于默认是最大堆所以还需自定义比较函数使得其按照权重升序排列。

struct cmp {
    bool operator()(const pair<int,int>& a,const pair<int,int>& b){
        return a.first>b.first;
    }
};

#### 初始化工作

设定起点的距离为0并将其加入到优先级队列里头作为初始状态准备开始遍历过程；其余各点均初始化成无穷大表示尚未访问过这些位置。

for (int i = 1; i <= n; ++i) dis[i]=INT_MAX;
dis[s]=0;
pq.push({0,s});

#### 主循环逻辑

当还有未处理完毕的数据存在于队首时就持续执行下面的操作直到全部完成为止：

- 取出堆顶记录即拥有目前所知最短路径长度的那个顶点u；
- 如果发现该处已被标记则跳过本轮迭代继续下一个；
- 否则枚举由这个新确认可达之处出发所能直接抵达的一切邻接站点v，并尝试更新它们之间的最优连接成本。

一旦成功改进了某条线路的信息，则立即将对应的更改推送到数据集合当中等待后续进一步考察验证。

while (!pq.empty()) {
    auto t=pq.top();
    pq.pop();

    int ver=t.second,dist=t.first;

    if (st[ver]) continue;
    st[ver]=true;

    for(int i=h[ver];~i;i=ne[i]){
        int j=e[i];
        if(dis[j]>dist+w[i]){
            dis[j]=dist+w[i];
            pq.push({dis[j],j});
        }
    }
}