负环与单源最短路计数

Prologue

  • 若图上存在一个环,环上各边的权值之和是负数,则称这个环是负环。

负环判定

​设 cnt[v] 表示从 11vv 的最短路径包含的边数,cnt[1]=0。当执行更新 d[v]=d[u]+w 时,同样更新 cnt[v]=cnt[u]+1。此时若发现 cnt[v]>=n,则图中有负环。若算法正常结束,则图中没有负环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int spfa() {
std::queue<int> q;q.push(1);
int u,v,w,d[_],cnt[_]={},inq[_]={};
memset(d,0x3f,sizeof(d));d[1]=0;
while(q.size()) {
u=q.front(),q.pop();inq[u]=0;
for(int i=hed[u];i;i=nxt[i])
if(d[v=ver[i]]>d[u]+(w=edg[i])) {
d[v]=d[u]+w;cnt[v]=cnt[u]+1;
if(cnt[v]>=n) return 1;
if(!inq[v]) q.push(v),inq[v]=1;
}
}
return 0;
}

关于 SPFA,它只活在负环判定。

最短路计数

正权图的最短路计数

​相比计算最短路只要多考虑两点:如果 dv=du+wuvd_v=d_u+w_{uv},根据加法原理,让 cnt[v]+=cnt[u];如果 dv>du+wuvd_v>d_u+w_{uv},令 cnt[v]=cnt[u]

1
2
3
4
5
6
7
8
9
10
11
12
void dijkstra() {
std::priority_queue<node> q;q.push((node){0,1});cnt[1]=1;
int u,vis[_]={};memset(d+2,0x3f,n<<2);
while(q.size()) {
u=q.top().second;q.pop();if(vis[u]) continue;vis[u]=1;
for(int v=1;v<=n;++v) {
if(d[u]+g[u][v]==d[v]) cnt[v]+=cnt[u];
if(d[u]+g[u][v]<d[v])
cnt[v]=cnt[u],d[v]=d[u]+g[u][v],q.push((node){-d[v],v});
}
}
}

负权图的最短路计数

​使用 SPFA 进行最短路计数较为复杂。大致过程为:

  • 如果当前取出的节点为终点直接跳过,没有必要用终点的最短路数去更新其他点的最短路数;
  • 如果 dv=du+wuvd_v=d_u+w_{uv} , 根据加法原理,让 cnt[v]+=cnt[u] 即可;
  • 如果 dv>du+wuvd_v>d_u+w_{uv} , 则边 uvuv 不满足三角形不等式,需要进行松弛,令 cnt[v]=cnt[u]
  • 只有 cnt[v]!=0 即存在从 11vv 的最短路的点才被入队。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void spfa() {
std::queue<int> q;q.push(1);cnt[1]=1;
int u,inq[_]={};memset(d,0x3f,sizeof(d));d[1]=0;
while(q.size()) {
u=q.front();q.pop();inq[u]=0;
if(u==n) continue;
for(int v=1;v<=n;++v) {
if(d[u]+g[u][v]==d[v]) cnt[v]+=cnt[u];
if(d[u]+g[u][v]<d[v])
cnt[v]=cnt[u],d[v]=d[u]+g[u][v];
if(!inq[v]&&cnt[v]) q.push(v),inq[v]=1;
}
cnt[u]=0;
}
}

行,SPFA 还活在一般的负权图。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 算法

评论

您需要成为穿墙的邪仙以加载 Disqus。