Johnson & dijkstra 跑费用流 学习笔记

基本思想

对于存在负权边的图，如果想跑 dijkstra，可以：

• 为每个点 $u$ 设置一个势能 $h_u$；
• 将边权为 $w$ 的边 $u\to v$ 的边权改为 $w+h_u-h_v$，这里要求选择的 $h$ 可以使得新图中所有边边权非负；
• 在新图中跑 dijkstra，最终 $x\to y$ 的实际最短路为 $dis_{x,y}-h_x+h_y$；

不难发现，对于 $h$ 的要求是：对于每条边 $(u\to v,w)$，满足 $w+h_u-h_v\ge 0$，也就是 $h_v\le h_u+w$。

注意到这个限制和最短路很像。那么直接在原图上随便找一个点 $s$，跑一次 SPFA 求出其到其他点的最短路 $dis_u$，并将 $h_u$ 设置成 $dis_u$ 即可。

但是可能随便找的 $s$ 到不了所有点，所以还有一种做法是建立一个超级源点 $s'$，从其向所有其它点连权值为 $0$ 的有向边，从这个点跑最短路即可。

Johnson 全源最短路

使用这种方法，建立超级源点 $s'$，跑一遍 SPFA 求出势能，再跑 $n$ 轮 dijkstra。

时间复杂度 $O(nm+nm\log n)$。

Primal-Dual 原始对偶求费用流

考虑从源点 $s$ 开始跑 SPFA，将其到每个点的最短路设为势能 $h$。

这样第一轮增广可以顺利跑 dijkstra。但问题是在增广时可能会删掉一些边，并增加对应的反向的负权边。

注意到修改的边 $(u\to v,w)$ 一定在 $s\to v$ 的最短路上，那么考虑设 $d_i$ 为新图（将 $w$ 变为 $w+h_u-h_v$ 后的图）中 $s\to i$ 的最短路，则结论是将下一轮每个点的势能 $h_i$ 修改为 $h_i+d_i$ 即可。

证明考虑对于原来的边，相当于在新图上再设置一次势能，显然边权依旧非负。

而对于新加的反向负权边 $(u\leftarrow v,-w)$，由于原来的正向边 $(u\to v,w)$ 一定在 $s\to v$ 的最短路上，故有 $d_u+(w+h_u-h_v)=d_v$，那么有 $(h_u+d_u)-(h_v+d_v)=-w$，所以 $-w+(h_v+d_v)-(h_u+d_u)=0$，那么在下一轮的新图上这条反向边的权值变为了 $0$，边权非负。

这样就可以保证费用流的时间复杂度是 $O(nm+fm\log n)$，其中 $f$ 为最大流。不过网络流模型的图一般卡不掉每次跑 SPFA 的 dinic。