Dijkstra堆优化的写法讨论
WorldBest丶牛顿
2018-09-12 23:34:41
## 本题解较适合堆优化重载括号运算符的同学看
众所周知, $Dijkstra$ 是一个常用来求没有负环的最短路的方法
一种常见的优化,就是优先队列(堆)优化 $Dijkstra$
优先队列的写法对每个人来说也是各不相同
针对一种重载括号运算符的写法,我想谈一谈我的看法
代码:
```cpp
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$
$cmp\quad$ 是重载括号运算符的写法
$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