Download presentation
Presentation is loading. Please wait.
1
Ford-Fulkerson's Labeling Algorithm
张梓悦
2
最大流的经典算法 每次使用BFS找增广路，保证找到的增广路是边 数最少的(即边权都为1时的最短路径)，也就是算 导上的Edmonds-Karp算法。可以证明，在使用 最短路增广时增广过程不超过|V|*|E|次，每次 BFS的时间都是O(|E|)，所以Edmonds-Karp 的时间复杂度就是O(|V|*|E|^2)。
3
sap算法——距离标记最短增广路算法 我们可以让每次寻找增广路时的时间复杂度降下 来，从而提高算法效率。
我们可以让每次寻找增广路时的时间复杂度降下 来，从而提高算法效率。 使用距离标号d的最短增广路算法就是这样的。所 谓距离标号 ，就是某个点到汇点最少的边数(即边 权值为1时某个点到汇点的最短路径长度)。 sap的优势就是每次计算距离的时候不是重新bfs 计算，而是充分利用以前的距离标号的信息。 时 间复杂度为O((|E|*|V|^2)
4
距离标号 （1）d[t] = 0； （2）d[i] = d[j] + 1 (如果边ij在残余网络Gf 中)；
每个点的初始标号可以在一开始用一次从汇点 沿所有反向边的BFS求出。
![距离标号 （1）d[t] = 0； （2）d[i] = d[j] + 1 (如果边ij在残余网络Gf 中)；](http://slidesplayer.com/slide/17347645/101/images/4/%E8%B7%9D%E7%A6%BB%E6%A0%87%E5%8F%B7+%EF%BC%881%EF%BC%89d%5Bt%5D+%3D+0%EF%BC%9B+%EF%BC%882%EF%BC%89d%5Bi%5D+%3D+d%5Bj%5D+%2B+1+%28%E5%A6%82%E6%9E%9C%E8%BE%B9ij%E5%9C%A8%E6%AE%8B%E4%BD%99%E7%BD%91%E7%BB%9CGf+%E4%B8%AD%29%EF%BC%9B.jpg "每个点的初始标号可以在一开始用一次从汇点 沿所有反向边的BFS求出。")
5
性质1: 性质2： 性质3： 性质4： 如果距离标号是有效的，那么d[i]便是残余网络中从点i 到汇点的距离的下限。
允许边：如果对于边Cf(i, j)>0,且d[i]= d[j]+1，那么称 为允许边 允许路：一条从源点到汇点的且有允许边组成的路径 允许路是从源点到汇点的最短增广路径。 性质3： 每次修改标号都会使距离标号严格递增 性质4： 当标号中出现了不连续标号的情况时，即已经不存在新 的增广流，此时的流量即为最大流。
![性质1: 性质2： 性质3： 性质4： 如果距离标号是有效的，那么d[i]便是残余网络中从点i 到汇点的距离的下限。](http://slidesplayer.com/slide/17347645/101/images/5/%E6%80%A7%E8%B4%A81%3A+%E6%80%A7%E8%B4%A82%EF%BC%9A+%E6%80%A7%E8%B4%A83%EF%BC%9A+%E6%80%A7%E8%B4%A84%EF%BC%9A+%E5%A6%82%E6%9E%9C%E8%B7%9D%E7%A6%BB%E6%A0%87%E5%8F%B7%E6%98%AF%E6%9C%89%E6%95%88%E7%9A%84%EF%BC%8C%E9%82%A3%E4%B9%88d%5Bi%5D%E4%BE%BF%E6%98%AF%E6%AE%8B%E4%BD%99%E7%BD%91%E7%BB%9C%E4%B8%AD%E4%BB%8E%E7%82%B9i+%E5%88%B0%E6%B1%87%E7%82%B9%E7%9A%84%E8%B7%9D%E7%A6%BB%E7%9A%84%E4%B8%8B%E9%99%90%E3%80%82.jpg "允许边：如果对于边Cf(i, j)>0,且d[i]= d[j]+1，那么称 为允许边. 允许路：一条从源点到汇点的且有允许边组成的路径. 允许路是从源点到汇点的最短增广路径。 性质3： 每次修改标号都会使距离标号严格递增. 性质4： 当标号中出现了不连续标号的情况时，即已经不存在新 的增广流，此时的流量即为最大流。")
6
算法思路 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.首先建立数组d ，d[i]表示节点 i 到汇点经过的最少路径数；](http://slidesplayer.com/slide/17347645/101/images/6/%E7%AE%97%E6%B3%95%E6%80%9D%E8%B7%AF+1.%E9%A6%96%E5%85%88%E5%BB%BA%E7%AB%8B%E6%95%B0%E7%BB%84d+%EF%BC%8Cd%5Bi%5D%E8%A1%A8%E7%A4%BA%E8%8A%82%E7%82%B9+i+%E5%88%B0%E6%B1%87%E7%82%B9%E7%BB%8F%E8%BF%87%E7%9A%84%E6%9C%80%E5%B0%91%E8%B7%AF%E5%BE%84%E6%95%B0%EF%BC%9B.jpg "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]的，出现断层，永远不能到达 汇点。")
7
算法流程 (1).从源点s开始，找下一个节点p，使得d[s]=d[p]+1。找到 后继续找p的下一个节点，到达汇点t时转(3)，否则转(2); (2).修改d值，重新到(1)； (3).根据本次找到的路径修改路径上的流量和反向边的流量， 若出现断层，停止该算法，否则重新到(1)。
![算法流程 (1).从源点s开始，找下一个节点p，使得d[s]=d[p]+1。找到 后继续找p的下一个节点，到达汇点t时转(3)，否则转(2); (2).修改d值，重新到(1)； (3).根据本次找到的路径修改路径上的流量和反向边的流量， 若出现断层，停止该算法，否则重新到(1)。](http://slidesplayer.com/slide/17347645/101/images/7/%E7%AE%97%E6%B3%95%E6%B5%81%E7%A8%8B+%281%29.%E4%BB%8E%E6%BA%90%E7%82%B9s%E5%BC%80%E5%A7%8B%EF%BC%8C%E6%89%BE%E4%B8%8B%E4%B8%80%E4%B8%AA%E8%8A%82%E7%82%B9p%EF%BC%8C%E4%BD%BF%E5%BE%97d%5Bs%5D%3Dd%5Bp%5D%2B1%E3%80%82%E6%89%BE%E5%88%B0+%E5%90%8E%E7%BB%A7%E7%BB%AD%E6%89%BEp%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E8%8A%82%E7%82%B9%EF%BC%8C%E5%88%B0%E8%BE%BE%E6%B1%87%E7%82%B9t%E6%97%B6%E8%BD%AC%283%29%EF%BC%8C%E5%90%A6%E5%88%99%E8%BD%AC%282%29%3B+%282%29.%E4%BF%AE%E6%94%B9d%E5%80%BC%EF%BC%8C%E9%87%8D%E6%96%B0%E5%88%B0%281%29%EF%BC%9B+%283%29.%E6%A0%B9%E6%8D%AE%E6%9C%AC%E6%AC%A1%E6%89%BE%E5%88%B0%E7%9A%84%E8%B7%AF%E5%BE%84%E4%BF%AE%E6%94%B9%E8%B7%AF%E5%BE%84%E4%B8%8A%E7%9A%84%E6%B5%81%E9%87%8F%E5%92%8C%E5%8F%8D%E5%90%91%E8%BE%B9%E7%9A%84%E6%B5%81%E9%87%8F%EF%BC%8C+%E8%8B%A5%E5%87%BA%E7%8E%B0%E6%96%AD%E5%B1%82%EF%BC%8C%E5%81%9C%E6%AD%A2%E8%AF%A5%E7%AE%97%E6%B3%95%EF%BC%8C%E5%90%A6%E5%88%99%E9%87%8D%E6%96%B0%E5%88%B0%281%29%E3%80%82.jpg "算法流程 (1).从源点s开始，找下一个节点p，使得d[s]=d[p]+1。找到 后继续找p的下一个节点，到达汇点t时转(3)，否则转(2); (2).修改d值，重新到(1)； (3).根据本次找到的路径修改路径上的流量和反向边的流量， 若出现断层，停止该算法，否则重新到(1)。")
8
sap算法演示 3 5 6 7 7 7 1 3 3 2 4 6 4 5 6
9
初始标号 2 1 6 7 7 3 3 3 2 2 1 4 5 6
10
可增广路 2 1 6 7 7 3 3 3 2 2 1 4 5 6
11
更新残存网络 2 1 6 6 6 1 1 3 3 3 2 2 1 4 5 6
12
可增广路 2 1 6 6 6 1 1 3 3 3 2 2 1 4 5 6
13
更新残存网络 2 1 7 6 6 1 3 1 1 2 3 2 2 1 3 5 6
14
寻找增广路->没有可进入边->更新标号
2 3 7 6 6 1 3 1 1 2 3 2 2 1 3 5 6
15
寻找增广路->没有可进入边->更新标号
4 3 7 6 6 1 3 1 1 2 3 2 2 1 3 5 6
16
寻找增广路->没有可进入边->更新标号
4 3 7 6 6 1 3 1 1 2 3 3 2 1 3 5 6
17
寻找增广路->没有可进入边->更新标号
4 3 7 6 6 1 4 1 1 2 3 3 2 1 3 5 6
18
可增广路 4 3 7 6 6 1 4 1 1 2 3 3 2 1 3 5 6
19
更新残存网络 4 3 7 6 6 1 4 1 3 4 2 3 2 1 3 3 2 3
20
寻找增广路->没有可进入边->更新标号
4 3 7 6 6 1 5 1 3 4 2 3 2 1 3 3 2 3
21
寻找增广路->没有可进入边->更新标号
6 3 7 6 6 1 5 1 3 4 2 3 2 1 3 3 2 3
22
可得最大流 3 5 6 7 7 6 1 1 3 2 4 6 4 3 3
23
其它距离标号算法——Dinic算法 Dinic算法的思想也是分阶段地在层次网络中增 广。它与Edmonds-Karp算法不同之处是：EK 算法在每个阶段执行完一次BFS增广后，要重 新启动BFS从源点s开始寻找另一条增广路。而 在Dinic算法中，只需一次DFS过程就可以实现 多次增广。
Similar presentations
