无论是HLPP还是ISAP的Gap优化,实际上都是极其类似的优化,都是寻找不到增广路了。

有时候经常会犯一个误区,为什么当$gap_{d_x}=0$了,就没有增广路了,难道比$d_x$小的点$i$不能通过累加使自己的层次达到$d_x$吗?

其实不然,首先思考$d_x$,代表一个最短距离(从$s$,或$t$),即$ i$所连出去的点$j$,$\forall d_j\le d_i+1 $ 。

因此对于$gap_{d_x}=0$,考虑有可能产生$d_x$的点$i$,就必须与$d_{x}-1$层次的点相连,且含有流量。

但是,如果$d_i\ne d_{x}-2$的话,$d_{x}-1$层次的点就不是$d_{x}-1$层次的点了(应该更小)。

如果$d_i={d_x}-2$的话,流量就会到$d_{x}-1$,而自己是不会更新的。

所以根据这个条件,当$gap_{d_x}=0 $时,不可能会有新的$d_x$层次的点。