流网络（Flow Networks）指的是一个有向图 G = (V, E)，其中每条边 (u, v) ∈ E 均有一非负容量 c(u, v) ≥ 0。如果 (u, v) ∉ E 则可以规定 c(u, v) = 0。流网络中有两个特殊的顶点：源点 s （source）和汇点 t（sink）。为方便起见，假定每个顶点均处于从源点到汇点的某条路径上，就是说，对每个顶点 v ∈ E，存在一条路径 s --> v --> t。因此，图 G 为连通图，且 |E| ≥ |V| - 1。
下图展示了一个流网络实例。
设 G = (V, E) 是一个流网络，其容量函数为 c。设 s 为网络的源点，t 为汇点。G 的流的一个实值函数 f：V×V → R，且满足下列三个性质：
- 容量限制（Capacity Constraint）：对所有顶点对 u, v ∈ V，要求 f(u, v) ≤ c(u, v)。
- 反对称性（Skew Symmetry）：对所有顶点对 u, v ∈ V，要求 f(u, v) = - f(v, u)。
- 流守恒性（Flow Conservation）：对所有顶点对 u ∈ V - {s, t}，要求 Σv∈Vf(u, v) = 0。
f(u, v) 称为从顶点 u 到顶点 v 的流，流的值定义为：|f| =Σv∈Vf(s, v)，即从源点 s 出发的总流。
最大流问题（Maximum-flow problem）中，给出源点 s 和汇点 t 的流网络 G，希望找出从 s 到 t 的最大值流。
满足流网络的性质的实际上定义了问题的限制：
- 经过边的流不能超过边的容量；
- 除了源点 s 和汇点 t，对于其它所有顶点，流入量与流出量要相等；
上面的图中描述的流网络可简化为下图，其中源点 s = 0，汇点 t = 5。
上图的最大流为 23，流向如下图所示。
Ford-Fulkerson 算法是一种解决最大流的方法，其依赖于三种重要思想：
- 残留网络（Residual networks）
- 增广路径（Augmenting paths）
- 割（Cut）
这些思想是最大流最小割定理的精髓，该定理用流网络的割来描述最大流的值。
最大流最小割定理
如果 f 是具有源点 s 和汇点 t 的流网络 G = (V, E) 中的一个流，则下列条件是等价的：
- f 是 G 的一个最大流。
- 残留网络 Gf 不包含增广路径。
- 对 G 的某个割 (S, T)，有 |f| = c(S, T)。
Ford-Fulkerson 算法是一种迭代方法。开始时，对所有 u, v ∈ V 有 f(u, v) = 0，即初始状态时流的值为 0。在每次迭代中，可通过寻找一条增广路径来增加流值。增广路径可以看做是从源点 s 到汇点 t 之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直至增广路径都被找出为止。最大流最小割定理将说明在算法终止时，这一过程可产生出最大流。
FORD-FULKERSON-METHOD(G, s, t)
initialize flow f to
while there exists an augmenting path p
do augment flow f along p
return f
上述伪码实现的时间复杂度为 O(max_flow * E)。
C# 代码实现如下：
using System;
using System.Collections.Generic;
using System.Linq; namespace GraphAlgorithmTesting
{
class Program
{
static void Main(string[] args)
{
Graph g = new Graph();
g.AddEdge(, , );
g.AddEdge(, , );
g.AddEdge(, , );
g.AddEdge(, , );
g.AddEdge(, , );
g.AddEdge(, , );
g.AddEdge(, , );
g.AddEdge(, , );
g.AddEdge(, , );
g.AddEdge(, , ); Console.WriteLine();
Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);
Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);
Console.WriteLine(); int maxFlow = g.FordFulkerson(, );
Console.WriteLine("The Max Flow is : {0}", maxFlow); Console.ReadKey();
} class Edge
{
public Edge(int begin, int end, int weight)
{
this.Begin = begin;
this.End = end;
this.Weight = weight;
} public int Begin { get; private set; }
public int End { get; private set; }
public int Weight { get; private set; } public override string ToString()
{
return string.Format(
"Begin[{0}], End[{1}], Weight[{2}]",
Begin, End, Weight);
}
} class Graph
{
private Dictionary<int, List<Edge>> _adjacentEdges
= new Dictionary<int, List<Edge>>(); public Graph(int vertexCount)
{
this.VertexCount = vertexCount;
} public int VertexCount { get; private set; } public IEnumerable<int> Vertices
{
get
{
return _adjacentEdges.Keys;
}
} public IEnumerable<Edge> Edges
{
get
{
return _adjacentEdges.Values.SelectMany(e => e);
}
} public int EdgeCount
{
get
{
return this.Edges.Count();
}
} public void AddEdge(int begin, int end, int weight)
{
if (!_adjacentEdges.ContainsKey(begin))
{
var edges = new List<Edge>();
_adjacentEdges.Add(begin, edges);
} _adjacentEdges[begin].Add(new Edge(begin, end, weight));
} public int FordFulkerson(int s, int t)
{
int u, v; // Create a residual graph and fill the residual graph with
// given capacities in the original graph as residual capacities
// in residual graph
int[,] residual = new int[VertexCount, VertexCount]; // Residual graph where rGraph[i,j] indicates
// residual capacity of edge from i to j (if there
// is an edge. If rGraph[i,j] is 0, then there is not)
for (u = ; u < VertexCount; u++)
for (v = ; v < VertexCount; v++)
residual[u, v] = ;
foreach (var edge in this.Edges)
{
residual[edge.Begin, edge.End] = edge.Weight;
} // This array is filled by BFS and to store path
int[] parent = new int[VertexCount]; // There is no flow initially
int maxFlow = ; // Augment the flow while there is path from source to sink
while (BFS(residual, s, t, parent))
{
// Find minimum residual capacity of the edhes along the
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
int pathFlow = int.MaxValue;
for (v = t; v != s; v = parent[v])
{
u = parent[v];
pathFlow = pathFlow < residual[u, v]
? pathFlow : residual[u, v];
} // update residual capacities of the edges and reverse edges
// along the path
for (v = t; v != s; v = parent[v])
{
u = parent[v];
residual[u, v] -= pathFlow;
residual[v, u] += pathFlow;
} // Add path flow to overall flow
maxFlow += pathFlow;
} // Return the overall flow
return maxFlow;
} // Returns true if there is a path from source 's' to sink 't' in
// residual graph. Also fills parent[] to store the path.
private bool BFS(int[,] residual, int s, int t, int[] parent)
{
bool[] visited = new bool[VertexCount];
for (int i = ; i < visited.Length; i++)
{
visited[i] = false;
} Queue<int> q = new Queue<int>(); visited[s] = true;
q.Enqueue(s);
parent[s] = -; // standard BFS loop
while (q.Count > )
{
int u = q.Dequeue(); for (int v = ; v < VertexCount; v++)
{
if (!visited[v]
&& residual[u, v] > )
{
q.Enqueue(v);
visited[v] = true;
parent[v] = u;
}
}
} // If we reached sink in BFS starting from source,
// then return true, else false
return visited[t] == true;
}
}
}
}
运行结果如下：
参考资料
- 广度优先搜索
- 深度优先搜索
- Breadth First Traversal for a Graph
- Depth First Traversal for a Graph
- Dijkstra 单源最短路径算法
- Bellman-Ford 单源最短路径算法
- Bellman–Ford algorithm
- Introduction To Algorithm
- Floyd-Warshall's algorithm
- Bellman-Ford algorithm for single-source shortest paths
- Dynamic Programming | Set 23 (Bellman–Ford Algorithm)
- Dynamic Programming | Set 16 (Floyd Warshall Algorithm)
- Johnson’s algorithm for All-pairs shortest paths
- Floyd-Warshall's algorithm
- 最短路径算法--Dijkstra算法，Bellmanford算法，Floyd算法，Johnson算法
- QuickGraph, Graph Data Structures And Algorithms for .NET
- CHAPTER 26: ALL-PAIRS SHORTEST PATHS
本篇文章《Ford-Fulkerson 最大流算法》由 Dennis Gao 发表自博客园，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。