本文主要是介绍算法导论——26.2 FordFulkerson方法，Edmonds-Karp算法java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
介绍
由Ford 和Fulkerson于1956年提出最大流问题的标号算法，故又称 Ford–Fulkerson标号法。其基本思想就是，从一个可行流开始，寻找从s到t的增广链，然而沿增广链增加流量，反复这样，直到找不出增广链位置。
更多内容参见博文http://blog.csdn.net/smartxxyx/article/details/9293665
这里值得注意的是，这个方法各种实现算法不同，基本上都取决于增广路径的寻找方式不同，而用bfs的方式找增广路径的方法就是Edmonds-Karp算法，这里借鉴了http://blog.csdn.net/smartxxyx/article/details/9293805的代码，并且对其做了注释，得到以下java代码。
package algorithms.maxflow;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;/*** @Description FordFulkerson方法中用edmondsKarp算法* Created with IntelliJ IDEA.* Created by The_Sam on 2017/5/9 11:27*/
public class FordFulkerson {private double residualNetwork[][] = null;private double flowNetwork[][] = null;int parent[]; //先驱节点/*** @param args*/public static void main(String[] args) {double graph[][] = {{0, 16, 13, 0, 0, 0},{0, 0, 10, 12, 0, 0},{0, 4, 0, 0, 14, 0},{0, 0, 9, 0, 0, 20},{0, 0, 0, 7, 0, 4},{0, 0, 0, 0, 0, 0}};double graph2[][] = {{0, 1000000, 1000000, 0},{0, 0, 1, 1000000},{0, 0, 0, 1000000},{0, 0, 0, 0},};FordFulkerson ff = new FordFulkerson();System.out.println(ff.edmondsKarpMaxFlow(graph2, 0, 3));}/*** 实现FordFulkerson方法的一种算法——edmondsKarp算法** @param graph* @param s* @param t* @return*/public double edmondsKarpMaxFlow(double graph[][], int s, int t) {// this.N = graph.length;int length = graph.length;parent = new int[length];double f[][] = new double[length][length];; //网络流for (int i = 0; i < length; i++) {Arrays.fill(f[i], 0);}double r[][] = residualNetwork(graph, f); //计算残余网络double result = augmentPath(r, s, t); //广度优先遍历，在残余网络中寻找增光路径，也是最短增广路径，得出该路径的流double sum = 0;while (result != -1) {int cur = t;while (cur != s) {//由后往前更新增广路径的流和残余网络f[parent[cur]][cur] += result;f[cur][parent[cur]] = -f[parent[cur]][cur];r[parent[cur]][cur] -= result;r[cur][parent[cur]] += result;cur = parent[cur];}sum += result; //最大流更新result = augmentPath(r, s, t); //广度优先遍历，在残余网络中寻找增光路径，也是最短增广路径，得出该路径的流}residualNetwork = r;flowNetwork = f;return sum;}/*** deepCopy 残余网络计算** @param cost* @param f* @return*/private double[][] residualNetwork(double cost[][], double f[][]) {int length = cost.length;double r[][] = new double[length][length];for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {r[i][j] = cost[i][j] - f[i][j];//残余网络=图cost-流f}}return r;}/*** 广度优先遍历，寻找增光路径，也是最短增广路径** @param graph* @param s* @param t* @return double 没有增广路径返回-1*/public double augmentPath(double graph[][], int s, int t) {double maxflow = Integer.MAX_VALUE;Arrays.fill(parent, -1);Queue<Integer> queue = new LinkedList<Integer>();queue.add(s);parent[s] = s;while (!queue.isEmpty()) {int p = queue.poll();if (p == t) {//如果到t了，则说明有了一条增广路径，则记录下该路径最小流，记为该增广路径可通过的最大流while (p != s) {if (maxflow > graph[parent[p]][p])maxflow = graph[parent[p]][p];p = parent[p];}} else { //记录最前面的前驱节点，如果没到最后t，切该节点没有记录过前驱节点，则记录该节点的前驱节点for (int i = 0; i < graph.length; i++) {if (i != p && parent[i] == -1 && graph[p][i] > 0) {//如果存在edge(p,i) 则记录parent[i]=p//flow[i]=Math.min(flow[p], graph[p][i]);parent[i] = p;queue.add(i);}}}}if (parent[t] == -1)//如果没有遍历到t节点，则不存在增广路径，返回-1return -1;return maxflow;}public double[][] getResidualNetwork() {return residualNetwork;}public double[][] getFlowNetwork() {return flowNetwork;}
}
这篇关于算法导论——26.2 FordFulkerson方法，Edmonds-Karp算法java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
