Primal-Dual 原始对偶算法学习笔记

Phartial · 2023-10-23 21:07:55 · 个人记录

Primal-Dual 原始对偶算法

Primal-Dual 原始对偶算法能够在较优的时间复杂度内求解最小费用最大流。

参考 Johnson 全源最短路算法的思想，我们为每个点设置一个势能 h_i，将原图上的有向边 (u,v,w) 变为 (u,v,w+h_u-h_v)。不难发现新图的最短路和原图是一样的。

那么我们只需要满足约束 w+h_u-h_v\ge 0，容易发现任意一点到其他点的距离 d_i 满足条件（如果 w+d_u-d_v<0，就有 d_v>d_u+w，即点 v 可以被更新成更优的答案，矛盾），我们可以初始时对其做一遍 SPFA 或 Dijkstra（仅适用于初始边权非负的情况）来求出 h_i。

那么我们每次增广时就可以用 Dijkstra 算法找到源点到汇点的最短路径，取出其上的瓶颈边并增广即可。

但是增广一次后原图的形态会发生改变，具体的，增广路上的边将会变为原来的反向边，同时边权取反。设 d_i 为源点到其他点的最短路，则：

• 对于增广路上的边 (i,j,w)，有 d_i+(w+h_i-h_j)=d_j，即 w+(h_i+d_i)-(h_j+d_j)=-w+(h_j+d_j)-(h_i+d_i)=0，原边和反向边边权都非负；
• 对于不在增广路上的边 (i,j,w) 也是类似，有 d_i+(w+h_i-h_j)\ge d_j，即 w+(h_i+d_i)-(h_j+d_j)\ge 0，同样非负。

综上，我们可以直接将残量网络上一个点 i 的势能更新为 h_i+d_i，且更新后边权仍然非负。

于是我们就可以用 Dijkstra 来求残量网络中的最短路了。