首页 > 图论 > 网络流 > 最大流问题-Ford-Fulkerson算法
2014
09-18

最大流问题-Ford-Fulkerson算法

问题:

有一个自来水管道运输系统,起点是s,终点是t,途中经过的管道都有一个最大的容量。求从s到t的最大水流量是多少?

网络最大流问题是网络的另一个基本问题。许多系统包含了流量问题。例如交通系统有车流量,金融系统有现金流,控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。

如下图所示:

ford_fulkerson11

 

最大的流量是 23:

ford_fulkerson2

 

比较常见的是Ford-Fulkerson解法。该方法依赖于三种重要思想:残留网络,增广路径和割。详细的介绍可以参考:

http://blog.csdn.net/smartxxyx/article/details/9293665

该算法可以简单的描述如下:

1) 初始化flow为0

2)While (存在从s到t的增广路径,设其流量为path-flow)

flow += path-flow;

更新残留网络;

3) return flow

Java代码如下:

import java.util.LinkedList;
import java.util.Queue;

public class MinFlow {
	public static int V = 6;

	/**
	 * 
	 * @param rGraph 残留网络
	 * @param s 源点
	 * @param t 终点
	 * @param path 路径
	 * @return 是否可以在rGraph中找到一条从 s 到 t 的路径
	 */
	public static boolean hasPath(int rGraph[][], int s, int t, int path[]) {
		boolean visited[] = new boolean[V];
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(s);
		visited[s] = true;
		//标准的BFS算法
		while(queue.size() > 0){
			int top = queue.poll();
			for(int i=0; i<V; i++){
				if(!visited[i] && rGraph[top][i] > 0){
					queue.add(i);
					visited[i] = true;
					path[i] = top;
				}

			}
		}
		return visited[t] == true;
	}

	/**
	 * 
	 * @param graph 有向图的矩阵表示
	 * @param s 源点
	 * @param t 终点
	 * @return 最大流量
	 */
	private static int maxFlow(int[][] graph,int s, int t) {
		int rGraph[][] = new int[V][V];
		for(int i=0; i<V; i++)
			for(int j=0; j<V; j++)
				rGraph[i][j] = graph[i][j];

		int maxFlow = 0;

		int path[] = new int[V];
		while(hasPath(rGraph, s, t, path)){
			int min_flow = Integer.MAX_VALUE;

			//更新路径中的每条边,找到最小的流量
			for(int v=t; v != s; v=path[v]){
				int u = path[v];
				min_flow = Math.min(min_flow, rGraph[u][v]);
			}

			//更新路径中的每条边
			for(int v=t; v != s; v=path[v]){
				int u = path[v];
				rGraph[u][v] -= min_flow;
				rGraph[v][u] += min_flow;
			}
			maxFlow += min_flow;
		}

		return maxFlow;
	}

	public static void main(String[] args) {
		//创建例子中的有向图
		int 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 } };
		V = graph.length;
		int flow = maxFlow(graph, 0, 5);
		System.out.println("The maximum possible flow is :" + flow);
	}
}

参考:http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。