ISAP算法对 Dinic算法的改进

时间:2021-11-06 10:01:09

ISAP算法对 Dinic算法的改进:
  在刘汝佳图论的开头引言里面,就指出了,算法的本身细节优化,是比较复杂的,这些高质量的图论算法是无数优秀算法设计师的智慧结晶。
如果一时半会理解不清楚,也是正常的。但是对于一个优秀的acmer来说,其算法的本身,可以锻炼你的思维。增长见识!

下面是我对 Dinic和ISAP的认识:

  Dinic算法比较值钱的 EK算法来说,已经有很大的提高了,其优势在哪里呢? 就是在于他的分层思想。在层次图上增广。但是,他也有弊端。
就是每次进行增广后,对于层次图都进行了从头再来。
  Dinic算法最大的优点就是概念简单,且速度不错!!!

如果效率要求很高,可以将Dinic算法改写成迭代形式。但是一般不这样做,而是采用 ISAP算法;

  ISAP算法就在刚刚的层次图上做了文章:
    1、首先层次图的定义有修改 d(i)表示到汇点的距离的下界,沿着可行流走,当我们找不到增广路的时候,在Dinic算法中,是一次性修改所有
  距离标号,而 ISAP只按增广边修改。这是第一个优化。注意,如果从结点 i 找不到增广路, d(i) >=n;
    2、gap优化:对于每一个距离标号d(i)=x;用一个num[x] 数组维护,就是指,x 这个距离标号的个数,如果某一个距离标号 num[x] = 0;
  一定就没有了增广路了。