求最大流有一种经典的算法，就是每次找增广路时用BFS找，保证找到的增广路是弧数最少的(即边权都为1时的最短路径)，也就是所谓的Edmonds-Karp算法。可以证明的是在使用最短路增广时增广过程不超过|V|*|E|次，每次BFS的时间都是O(|E|)，所以Edmonds-Karp的时间复杂度就是O(|V|*|E|^2)。
如果能让每次寻找增广路时的时间复杂度降下来，那么就能提高算法效率了，使用距离标号d（有时候称为"高度h"）的最短增广路算法就是这样的。所谓距离标号 ，就是某个点到汇点的最少的弧的数量（即边权值为1时某个点到汇点的最短路径长度） 。设点i的标号为d[i]，那么如果将满足d[i]=d[j]+1的弧(i,j)叫做允许弧 ，且增广时只走允许弧，那么就可以达到"怎么走都是最短路"的效果 。每个点的初始标号可以在一开始用一次从汇点沿所有反向边的BFS求出，实践中可以初始设全部点的距离标号为0，问题就是如何在增广过程中维护这个距离标号。
Sam评注：
(1).
外国大牛的文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited#1 中有这样一句话非常重要："We can distance function exactly if each i in V, d[i] equals the length of the shortest path from i to t(sink) in the residual network."
上面这句话意思是说：只有当d[i]恰好等于i到汇点t的最短路径（边权都为1）时，才称d为"距离函数"。而每次用SAP寻找增广路径初始，d[i] (i∈V)都被初始化为0。因此一开始，只有汇点的距离函数d[t]=0满足这个条件；对其他顶点，d[i]只能称为"i的距离函数值的下界/估计"，因为它<真正的d[i]。于是，外国大牛又冒出这样一句话：
"It is also easy to prove that if d(s)≥|V|, then the residual network contains no path from the source to the sink."
(2).
寻找一条最短（边最少）增广路径中用到的"递归机制"，实际上保证了最短路径的层次图是从汇点向源点扩展的。而每次用SAP寻找一条增广路径开始时，d[t]=0已经是真正的最短路径，因此如果有最短增广路径，完成SAP搜索后d[i]=真正的最短路径。
Read full article from 最大流（二）――SAP算法 - 滩涂曳尾 - ITeye技术网站
No comments:
Post a Comment