Ford-Fulkerson's Labeling Algorithm 171860578 张梓悦
最大流的经典算法 每次使用BFS找增广路，保证找到的增广路是边 数最少的(即边权都为1时的最短路径)，也就是算 导上的Edmonds-Karp算法。可以证明，在使用 最短路增广时增广过程不超过|V|*|E|次，每次 BFS的时间都是O(|E|)，所以Edmonds-Karp 的时间复杂度就是O(|V|*|E|^2)。
sap算法——距离标记最短增广路算法 我们可以让每次寻找增广路时的时间复杂度降下 来，从而提高算法效率。 我们可以让每次寻找增广路时的时间复杂度降下 来，从而提高算法效率。 使用距离标号d的最短增广路算法就是这样的。所 谓距离标号 ，就是某个点到汇点最少的边数(即边 权值为1时某个点到汇点的最短路径长度)。 sap的优势就是每次计算距离的时候不是重新bfs 计算，而是充分利用以前的距离标号的信息。 时 间复杂度为O((|E|*|V|^2)
距离标号 （1）d[t] = 0； （2）d[i] = d[j] + 1 (如果边ij在残余网络Gf 中)； 每个点的初始标号可以在一开始用一次从汇点 沿所有反向边的BFS求出。
性质1: 性质2： 性质3： 性质4： 如果距离标号是有效的，那么d[i]便是残余网络中从点i 到汇点的距离的下限。 允许边：如果对于边Cf(i, j)>0,且d[i]= d[j]+1，那么称 为允许边 允许路：一条从源点到汇点的且有允许边组成的路径 允许路是从源点到汇点的最短增广路径。 性质3： 每次修改标号都会使距离标号严格递增 性质4： 当标号中出现了不连续标号的情况时，即已经不存在新 的增广流，此时的流量即为最大流。
算法思路 1.首先建立数组d ，d[i]表示节点 i 到汇点经过的最少路径数； 2.在一次寻找可行路径的过程中，若此时已到达 i 点，对于 边ij，若d[i]=d[j]+1，则j为可选点，这样可保证每次找到的 到达t的路径所经过的边数是最少的； 3.某时刻，在到达i处，不存在边ij使得d[i]=d[j]+1,则修改d[i]， 设i的所有后继的最小d为t，则修改d[i]=t+1； 4.设num[x]为d值为x的点的个数。对于一点i，在修改d[i]时， 若num[d[i]]=1则停止。因为修改了d[i]，num[d[i]]=0，d[i] 的值变大了，没有了大小为d[i]的，出现断层，永远不能到达 汇点。
算法流程 (1).从源点s开始，找下一个节点p，使得d[s]=d[p]+1。找到 后继续找p的下一个节点，到达汇点t时转(3)，否则转(2); (2).修改d值，重新到(1)； (3).根据本次找到的路径修改路径上的流量和反向边的流量， 若出现断层，停止该算法，否则重新到(1)。
sap算法演示 3 5 6 7 7 7 1 3 3 2 4 6 4 5 6
初始标号 2 1 6 7 7 3 3 3 2 2 1 4 5 6
可增广路 2 1 6 7 7 3 3 3 2 2 1 4 5 6
更新残存网络 2 1 6 6 6 1 1 3 3 3 2 2 1 4 5 6
可增广路 2 1 6 6 6 1 1 3 3 3 2 2 1 4 5 6
更新残存网络 2 1 7 6 6 1 3 1 1 2 3 2 2 1 3 5 6
寻找增广路->没有可进入边->更新标号 2 3 7 6 6 1 3 1 1 2 3 2 2 1 3 5 6
寻找增广路->没有可进入边->更新标号 4 3 7 6 6 1 3 1 1 2 3 2 2 1 3 5 6
寻找增广路->没有可进入边->更新标号 4 3 7 6 6 1 3 1 1 2 3 3 2 1 3 5 6
寻找增广路->没有可进入边->更新标号 4 3 7 6 6 1 4 1 1 2 3 3 2 1 3 5 6
可增广路 4 3 7 6 6 1 4 1 1 2 3 3 2 1 3 5 6
更新残存网络 4 3 7 6 6 1 4 1 3 4 2 3 2 1 3 3 2 3
寻找增广路->没有可进入边->更新标号 4 3 7 6 6 1 5 1 3 4 2 3 2 1 3 3 2 3
寻找增广路->没有可进入边->更新标号 6 3 7 6 6 1 5 1 3 4 2 3 2 1 3 3 2 3
可得最大流 3 5 6 7 7 6 1 1 3 2 4 6 4 3 3
其它距离标号算法——Dinic算法 Dinic算法的思想也是分阶段地在层次网络中增 广。它与Edmonds-Karp算法不同之处是：EK 算法在每个阶段执行完一次BFS增广后，要重 新启动BFS从源点s开始寻找另一条增广路。而 在Dinic算法中，只需一次DFS过程就可以实现 多次增广。