算法#18--最大流量问题（网络流算法）.md

算法#18--最大流量问题（网络流算法）

1.物理模型

请想象一组相互连接大小不一的输油管道，每根管道有它自己的流量和容量，问从起点到终点的最大流量是多少？如下流量图中，深色路径流量之和为最大路径。如何求得，下面内容将详细介绍。

2.数学模型

一个流量网络，是一张边的权重（这里称为容量）为正的**加权有向图**。一个st-流量网络有两个已知的顶点，即起点s和终点t。

3.Ford-Fulkerson算法

也称为增广路径算法。它的定义是：网络中的初始流量为零，沿着任意从起点到终点（且不含有饱和的正向边或是空逆向边）的增广路径增大流量，直到网络中不存在这样的路径为止。

也即，假设x为该路径上的所有边中未使用容量的最小值，那么只需将所有边的流量增大x，即可将网络中的总流量至少增大x。反复这个过程，直到所有起点到终点的路径上至少有一条边是饱和的。

4.剩余网络

这里，与流量对应的边的方向和流量本身相反。代码如下FlowNetwork类。

5.代码实现

对Ford-Fulkerson算法最简单的实现可能就是最短增广路径算法了（最短指的是路径长度最小，而非流量或是容量）。增广路径的查找等价于剩余网络中的广度优先搜索（BFS）。

public class FordFulkerson 
{
	private boolean[] marked;	//在剩余网络中是否存在从s到v的路径
	private FlowEdge[] edgeTo;	//从s到v的最短路径上的最后一条边
	private double value; 		//当前最大流量
	
	public FordFulkerson(FlowNetwork G, int s, int t)
	{	//找出从s到t的流量网络G的最大流量配置
		while(hasAugmentingPath(G, s, t))
		{	//利用所有存在的增广路径
			//计算当前的瓶颈容量
			double bottle = Double.POSITIVE_INFINITY;
			for(int v = t; v != s; v = edgeTo[v].other(v))
			{
				bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
			}
			//增大流量
			for(int v = t; v != s; v = edgeTo[v].other(v))
			{
				edgeTo[v].addResidualFlowTo(v, bottle);
			}
			value += bottle;
		}		
	}
	
	private boolean hasAugmentingPath(FlowNetwork G, int s, int t)
	{
		marked = new boolean[G.V()];	//标记路径已知的顶点
		edgeTo = new FlowEdge[G.V()]; 	//路径上的最后一条边
		Queue<Integer> q = new Queue<Integer>();
		
		marked[s] = true;	//标记起点
		q.enqueue(s); 		//并将它入列
		while(!q.isEmpty())
		{
			int v = q.dequeue();
			for(FlowEdge e : G.adj(v))
			{
				int w = e.other(v);
				if(e.residualCapacityTo(w) > 0 && !marked[w])
				{//(在剩余网络中)对于任意一条连接到一个未标记的顶点的边
					edgeTo[w] = e;	//保持路径上的最后一条边
					marked[w] = true;	//标记w，因为路径现在是已知的了
					q.enqueue(w);	//将它入列
				}
			}
		}
		return marked[t];
	}
	
	public double value()
	{
		return value;
	}
	
	public boolean inCut(int v)
	{
		return marked[v];
	}
	
	public static void main(String[] args)
	{
		FlowNetwork G = new FlowNetwork(6);
		int[] from = new int[]{0, 0, 1, 1, 2, 2, 3, 4};
		int[] to = new int[]{1, 2, 3, 4, 3, 4, 5, 5};
		double[] capacity = new double[]{2.0, 3.0, 3.0, 1.0, 1.0, 1.0, 2.0, 3.0};
		for(int i = 0; i < from.length; i++)
		{
			FlowEdge edge = new FlowEdge(from[i], to[i], capacity[i]);
			G.addEdge(edge);
		}		
		
		int s = 0, t = G.V() - 1;
		FordFulkerson maxflow = new FordFulkerson(G, s, t);
		System.out.println("Max flow from " + s + " to " + t);
		for(int v = 0; v < G.V(); v++)
		{
			for(FlowEdge e : G.adj(v))
			{
				if(v == e.from() && e.flow() > 0)
				{
					System.out.println(" " + e);
				}
			}
		}
		System.out.println("Max flow value = " + maxflow.value());
	}
}

输出：

Max flow from 0 to 5
 0->2 3.00 2.00
 0->1 2.00 2.00
 1->4 1.00 1.00
 1->3 3.00 1.00
 2->4 1.00 1.00
 2->3 1.00 1.00
 3->5 2.00 2.00
 4->5 3.00 2.00
Max flow value = 4.0

剩余网络类，其中的FlowEdge类的基础是加权边有向边。

public class FlowNetwork 
{
	private final int V;
	private int E;
	private Bag<FlowEdge>[] adj;
	
	@SuppressWarnings("unchecked")
	public FlowNetwork(int V)
	{
		this.V = V;
		this.E = 0;
		adj = (Bag<FlowEdge>[]) new Bag[V];
		for(int v = 0; v < V; v++)
		{
			adj[v] = new Bag<FlowEdge>();
		}
	}
	
	public int V()
	{
		return V;
	}
	
	public int E()
	{
		return E;
	}
	
	public void addEdge(FlowEdge e)
	{
		int v = e.either(), w = e.other(v);
		adj[v].add(e);
		adj[w].add(e);
		E++;
	}
	
	public Iterable<FlowEdge> adj(int v)
	{
		return adj[v];
	}
	
	public Iterable<FlowEdge> edges()
	{
		Bag<FlowEdge> b = new Bag<FlowEdge>();
		for(int v = 0; v < V; v++)
		{
			for(FlowEdge e : adj[v])
			{
				if(e.other(v) > v)
				{
					b.add(e);
				}
			}
		}
		return b;
	}
}

public class FlowEdge 
{
	private final int v;
	private final int w;
	private final double capacity;
	private double flow;
	
	public FlowEdge(int v, int w, double capacity)
	{
		this.v = v;
		this.w = w;
		this.capacity = capacity;
		this.flow = 0;
	}
	
	public int from()
	{
		return v;
	}
	
	public int to()
	{
		return w;
	}
	
	public double capacity()
	{
		return capacity;
	}
	
	public double flow()
	{
		return flow;
	}
	
	public int either()
	{
		return v;
	}
	
	public int other(int vertex)
	{
		if(vertex == v)
		{
			return w;
		}
		else if(vertex == w)
		{
			return v;
		}
		else
		{
			throw new RuntimeException("Inconsistent edge");
		}
	}
	
	public double residualCapacityTo(int vertex)
	{
		if(vertex == v)
		{
			return flow;
		}
		else if(vertex == w)
		{
			return capacity - flow;
		}
		else
		{
			throw new RuntimeException("Inconsistent edge");
		}
	}
	
	public void addResidualFlowTo(int vertex, double delta)
	{
		if(vertex == v)
		{
			flow -= delta;
		}
		else if(vertex == w)
		{
			flow += delta;
		}
		else
		{
			throw new RuntimeException("Inconsistent edge");
		}
	}
	
	public String toString()
	{
		return String.format("%d->%d %.2f %.2f", v, w, capacity, flow);
	}
}