优化扩展——重贴标签算法ISAP

首先对所有的结点标记到汇点的最短距离,称之为高度。标高从汇点开始,用BFS方式,汇点的邻接点高度为1,继续访问的结点高度是2,一直到源点结束。

贴好标签之后,就可以从源点开始,沿着高度h(u)=h(v)+1且具有可行邻接边(cap>flow)的方向前进。我们找到了1-2-4-6。

我们再次从源点开始搜索,沿着高度h(u)=h(v)+1且具有可行邻接边(cap>flow)的方向前进,h(1)=3,h(2)=2,走到这里无法走到4号结点,因为没有邻接边,3号结点不近没有邻接边,而且高度也不满足条件,也不能走到1号结点,怎么办呢?

可以用重贴标签的方法。当前结点无法前进时,令当前结点的高度=所有邻接点高度的最小值+1;如果没有邻接边,则令当前结点的高度=结点数;退回一步,重新搜索。

算法设计

  1. 确定合适的数据结构。采用邻接表存储网络。
  2. 对网络结点贴标签,即标高操作。
  3. 如果源点的高度≥结点数,则转向第6步;否则从源点开始,沿着高度h(u)=h(v)+1且具有可行邻接边(cap>flow)的方向前进,如果到达汇点,则转向第4步;如果无法进行,则第5步。
  4. 增流操作:沿着找到的可增广路同向边增流,反向边减流。注意:在原网络上操作
  5. 重贴标签:如果拥有当前结点高度的结点只有一个,转向第6步;令当前结点的高度=所有邻接点高度的最小值+1;如果没有邻接边,则令当前结点的高度=结点数;退回一步;转向第3步。
  6. 算法结束,已经找到最大流。

算法实现

算法复杂度分析
时间复杂度:找到一条可增广路时间为O(V),最多会执行O(VE)次,因为关键边的总数为O(VE),因此总的时间复杂度为O(V2E),其中V为结点个数,E为边的数量。

空间复杂度O(V)。

最小费用路算法——最小费用最大流

问题分析

除了流量之外,还定义了一个单位流量的费用。对于网络上的一个流flow,其费用为

$\cos t(flow)=\sum\limits_{<x,y>\in E}{\cos t(x,y)*flow(x,y)}$

网络流的费用=单位流量费用*每条边的流量

算法设计

有两种思路:
1. 先找最小费用路,在该路径上增流,增加到最大流,称为最小费用路算法
2. 先找最大流,然后找负费用圈,消减费用,减少到最小费用,称为消圈算法
最小费用路算法,是在残余网络上寻找从源点到汇点的最小费用路,即从源点到汇点的以单位费用为权的最短路,然后沿着最小费用路增流,直到找不到最小费用路为止。

算法解释

  1. 创建混合网络。先初始化为零流,零流对应混合网络中,正向边容量为cap,流量为0,费用为cost,反向边容量为0,流量为0,费用为-cost。
  2. 找最小费用路。先初始化每个结点的距离为无穷大,然后令源点的距离dist[v1]=0。在混合网络中,从源点出发,沿可行边(E[i].cap>E[i].flow)广度搜索每个邻接点,如果当前距离dist[v]>dist[u]+E[i].cost,则更新为最短距离:dist[v]=dist[u]+E[i].cost,并记录前驱。根据前驱数组,找到一条最短费用路,增广路经:1-2-5-6
  3. 然后沿着增广路经正向增流d,反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow),增流量d=3,产生费用为mincost+=dist[v6]d=83=24。
  4. 找最小费用路。先初始化每个结点距离为无穷大,然后令源点的距离dist[v1]=0。在混合网络中,从源点出发,沿可行边(E[i].cap>E[i].flow)广度搜索每个邻接点,如果当前距离dist[v]>dist[u]+E[i].cost,则更新为最短距离:dist[v]=dist[u]+E[i].cost,并记录前驱。根据前驱数组,找到一条最短费用路,增广路经:1-3-4-6
  5. 然后沿着增广路经正向增流d,反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow),增流量d=4,产生费用为mincost+=24+dist[v6]d=24+164=88。
  6. 找最小费用路。先初始化每个结点距离为无穷大,然后令源点的距离dist[v1]=0。在混合网络中,从源点出发,沿可行边(E[i].cap>E[i].flow)广度搜索每个邻接点,发现从源点出发已经没有可行边,结束,得到的网络流就是最小费用最大流。把混合网络中flow>0的边输出,就是我们要的实流网络。

代码实现

(1)定义结构体。结构体的定义与ISAP中结构体相同,边只是多了一个cost域,fisrt指向第一个邻接边,next是吓一跳邻接边,该结构体用于创建邻接表。

(2)创建残余网络边。正向边的容量为cap,流量为0,费用为cost,反向边容量为0,流量为0,费用为-cost。

(3)求最小费用路。先初始化每个结点距离无穷大,然后令源点的距离dist[v1]=0。在混合网络中,从源点出发,沿可行边(E[i].cap>E[i].flow)广度搜索每个邻接点,如果当前距离dist[v]>dist[u]+E[i].cost,则更新为最短距离:dist[v]=dist[u]+E[i].cost,并记录前驱。

(4)沿着最小费用路增流。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow)。沿着增广路径正向边增流d,反向边减流d,产生费用为mincost+=dist[t]*d。

复杂度分析

  1. 时间复杂度:找到一条可增广路时间为O(E),最多会执行O(VE)次,因为关键边的总数为O(VE),因此总的时间复杂度为O(VE2),其中V为结点个数,E为边的数量。
  2. 空间复杂度:O(V)。

消圈算法

算法设计
三个过程:

  1. 找给定网络的最大流。
  2. 在最大流对应的混合网络找负费用圈。
  3. 消负费用圈:负费用圈同方向的边流量加d,反方向的边流量减d。d为负费用圈所有边的最小可增量cap-flow。

算法的核心是在残余网络中找负费用圈。

算法解释

  1. 求最大流。用最大流求解算法求解最大流。
  2. 在最大流对应的混合网络中找负费用圈。在最大流的混合网络中,沿着cap>flow的边找负费用圈,就是各边费用之和为负的圈。
  3. 负费用圈同方向的边流量加d,反方向的边流量减d。沿找到的负费用全增流,其增量为组成负费用圈的所有边的最小可增量cap-flow。负费用圈说明费用较高,可以对费用为负的边减流,因为该残余网络为特殊的残余网络,负费用的边流量也是负值,减流实际上需要加上增流量d,为了维持平衡性,负费用圈同方向的边流量加d,反方向的边流量减d。
  4. 在混合网络中继续找负费用圈。在混合网络中,沿着cap>flow的边找负费用圈,已经找不到负费用圈,算法结束。把混合网络中flow>0的边输出,就是我们需要的实流网络。

复杂度分析

  1. 时间复杂度:最大流方法为O(V2E),如果每次消去负费用圈至少使费用下降一个单位,最多执行ECM此找负费用圈和增减流操作(C为每条边费用上界,M为每条边容量上界)。该算法时间复杂度为O(V2E2CM)。
  2. 空间复杂度O(V)。