Dijkstra堆优化的写法讨论

· · 题解

本题解较适合堆优化重载括号运算符的同学看

众所周知， Dijkstra 是一个常用来求没有负环的最短路的方法
一种常见的优化，就是优先队列（堆）优化 Dijkstra
优先队列的写法对每个人来说也是各不相同
针对一种重载括号运算符的写法，我想谈一谈我的看法

代码：

struct cmp{
    bool operator()(const int &x,const int &y)
    const
    {
        return dis[x]>dis[y];
    }
};
priority_queue<int,vector<int>,cmp>q;
void dijkstra(){
    int u,v,w;
    for(int i=1;i<=n;++i) d[i]=2147483647;
    dis[s]=0;q.push(s);
    while(!q.empty()){
        u=q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];i;i=p[i].nxt){
            v=p[i].to;w=p[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                q.push(v);
            }
        }                   
    }   
}

这种写法保留了 priority\_queue 中小根堆原来的写法，更容易理解
并且这种写法在某本著名的书中也出现了
但是这种方法真的没有问题吗？

我们可以考虑，如果在更新其他节点的时候，某一个节点被多次更新，那么它每次的 dis 值都是会减小的
那么如果一个节点更新的次数足够多时，它总有一次会跟自己进行比较，那么它会因为自己与自己的 dis 值相等而留在这个位置
那么它就会在堆中形成一种类似于“路障”的东西将堆的某些部分“堵住”
而这种写法在数据结构上也破坏了堆原有的性质，就会使算法出现错误
如下图：

q.push$ 表示松弛时的入堆操作， $1(10)$ 表示将节点编号为 $1$ 的 $dis$ 值修改为 $10 $node\quad$ 是将节点编号和 $dis$ 值合并之后的写法（下面有代码） 注： $pair$ 写法与 $node$ 写法大致类似，在此不再阐述 ![](https://cdn.luogu.com.cn/upload/pic/32719.png) 很明显，当编号为 $2$ 的节点多次入堆之后，堆内元素已经产生了问题 所以，如果一张图中有大量的重边，就很容易会导致这样的问题发生 附上 $node$ 写法代码 ```cpp struct node { int u,d; bool operator<(const node& rhs) const { return d>rhs.d; } }; void Dijkstra() { priority_queue<node> q; for(int i=1;i<=n;++i) d[i]=2147483647; q.push((node){s,d[s]}); d[s]=0; while(!q.empty()) { node x=q.top(); int u=x.u; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v,w=e[i].w; if(d[u]+w<d[v]) { d[v]=d[u]+w; q.push((node){v,d[v]}); } } } } ``` 如果有什么更好（玄学）的重载括号运算符的写法可以私信我qwq