学步园

Wikipedia 上关于Ford-Fulkerson算法的描述如下

Algorithm
Ford-Fulkerson

Inputs
Graph
with flow capacity
, a source node
, and a sink node

Output
A flow
from
to
which is a maximum

1. 
   for all edges
2. While there is a path
   from
   to
   in
   , such that
   for all edges
   :
   1. Find
   2. For each edge
      1. 
         (Send flow along the path
         )
      2. 
         (The flow might be "returned" later
         )

虽然算法貌似很简单，但是算法正确性的证明过程确实比较困难，由于本人才疏学浅，所以证明过程虽然看了好多便，现在仍然不甚明了，今天太晚了，明天继续搞，先把今晚用残量图实现的Ford-Fulkerson算法贴出来，注释比较详细。

package com.FeeLang;<br /> public class FordFulkerson {<br /> public static void main(String[] args){<br /> // int[][] net = new int[4][4];<br /> // net[0][1] = 1000;<br /> // net[0][2] = 1000;<br /> // net[1][2] = 1;<br /> // net[1][3] = 1000;<br /> // net[2][3] = 1000;<br /> int nodes = 6;<br /> int[][] capacity = new int[nodes][nodes];<br /> capacity[0][1] = 7;<br /> capacity[0][2] = 6;<br /> capacity[1][3] = 4;<br /> capacity[1][4] = 2;<br /> capacity[2][3] = 2;<br /> capacity[2][4] = 3;<br /> capacity[3][5] = 9;<br /> capacity[4][5] = 5;<br /> FordFulkerson maxFlow = new FordFulkerson(capacity, nodes);<br /> int max = maxFlow.getMaxFlow(0, 5);<br /> System.out.println(max);<br /> }</p> <p> public FordFulkerson(int[][] net, int nodes){<br /> this.net = net;<br /> this.nodes = nodes;</p> <p> pre = new int[nodes];<br /> visited = new boolean[nodes];</p> <p> }</p> <p> public int getMaxFlow(int s, int t){<br /> //initial the residual capacities<br /> residual = net;<br /> int maxFlow = 0;<br /> while (true){<br /> for (int i = 0; i < nodes; i++)<br /> visited[i] = false;<br /> //initial residual capacities<br /> getPath(s, t);<br /> if (!visited[t]){ // not find a path from s to t<br /> break;<br /> }</p> <p> //get the min capacity of the path<br /> int min = Integer.MAX_VALUE;<br /> for (int i = t; i > s; i = pre[i]){<br /> min = Math.min(min, residual[pre[i]][i]);<br /> }</p> <p> //send min units of flow to the path.<br /> //Update residual capacities<br /> for (int i = t; i > s; i = pre[i]){<br /> residual[pre[i]][i] -= min;<br /> residual[i][pre[i]] += min;<br /> }<br /> maxFlow += min;<br /> }</p> <p> return maxFlow;<br /> }</p> <p> //search a path from s to t<br /> public void getPath(int s, int t){<br /> visited[s] = true;<br /> for (int i = 0; i < nodes; i++){<br /> if (!visited[i] && residual[s][i] > 0){<br /> visited[i] = true;<br /> pre[i] = s;<br /> getPath(i, t);<br /> }<br /> }<br /> }</p> <p> private boolean[] visited;<br /> private int[][] net;<br /> private int[][] residual;<br /> private int[] pre;<br /> private int nodes; <br />