Ford-Fulkerson 最大流演算法

流網路（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 演算法是一種解決最大流的方法，其依賴於三種重要思想：

1. 殘留網路（Residual networks）
2. 增廣路徑（Augmenting paths）
3. 割（Cut）

這些思想是最大流最小割定理的精髓，該定理用流網路的割來描述最大流的值。

最大流最小割定理

如果 f 是具有源點 s 和匯點 t 的流網路 G = (V, E) 中的一個流，則下列條件是等價的：

1. f 是 G 的一個最大流。
2. 殘留網路 Gf 不包含增廣路徑。
3. 對 G 的某個割 (S, T)，有 |f| = c(S, T)。

Ford-Fulkerson 演算法是一種迭代方法。開始時，對所有 u, v ∈ V 有 f(u, v) = 0，即初始狀態時流的值為 0。在每次迭代中，可通過尋找一條增廣路徑來增加流值。增廣路徑可以看做是從源點 s 到匯點 t 之間的一條路徑，沿該路徑可以壓入更多的流，從而增加流的值。反覆進行這一過程，直至增廣路徑都被找出為止。最大流最小割定理將說明在演算法終止時，這一過程可產生出最大流。

1 FORD-FULKERSON-METHOD(G, s, t)n2 initialize flow f to 0n3 while there exists an augmenting path pn4 do augment flow f along pn5 return fn

上述偽碼實現的時間複雜度為 O(max_flow * E)。

C# 代碼實現如下：

1 using System;n 2 using System.Collections.Generic;n 3 using System.Linq;n 4 n 5 namespace GraphAlgorithmTestingn 6 {n 7 class Programn 8 {n 9 static void Main(string[] args)n 10 {n 11 Graph g = new Graph(6);n 12 g.AddEdge(0, 1, 16);n 13 g.AddEdge(0, 2, 13);n 14 g.AddEdge(1, 2, 10);n 15 g.AddEdge(1, 3, 12);n 16 g.AddEdge(2, 1, 4);n 17 g.AddEdge(2, 4, 14);n 18 g.AddEdge(3, 2, 9);n 19 g.AddEdge(3, 5, 20);n 20 g.AddEdge(4, 3, 7);n 21 g.AddEdge(4, 5, 4);n 22 n 23 Console.WriteLine();n 24 Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);n 25 Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);n 26 Console.WriteLine();n 27 n 28 int maxFlow = g.FordFulkerson(0, 5);n 29 Console.WriteLine("The Max Flow is : {0}", maxFlow);n 30 n 31 Console.ReadKey();n 32 }n 33 n 34 class Edgen 35 {n 36 public Edge(int begin, int end, int weight)n 37 {n 38 this.Begin = begin;n 39 this.End = end;n 40 this.Weight = weight;n 41 }n 42 n 43 public int Begin { get; private set; }n 44 public int End { get; private set; }n 45 public int Weight { get; private set; }n 46 n 47 public override string ToString()n 48 {n 49 return string.Format(n 50 "Begin[{0}], End[{1}], Weight[{2}]",n 51 Begin, End, Weight);n 52 }n 53 }n 54 n 55 class Graphn 56 {n 57 private Dictionary<int, List<Edge>> _adjacentEdgesn 58 = new Dictionary<int, List<Edge>>();n 59 n 60 public Graph(int vertexCount)n 61 {n 62 this.VertexCount = vertexCount;n 63 }n 64 n 65 public int VertexCount { get; private set; }n 66 n 67 public IEnumerable<int> Verticesn 68 {n 69 getn 70 {n 71 return _adjacentEdges.Keys;n 72 }n 73 }n 74 n 75 public IEnumerable<Edge> Edgesn 76 {n 77 getn 78 {n 79 return _adjacentEdges.Values.SelectMany(e => e);n 80 }n 81 }n 82 n 83 public int EdgeCountn 84 {n 85 getn 86 {n 87 return this.Edges.Count();n 88 }n 89 }n 90 n 91 public void AddEdge(int begin, int end, int weight)n 92 {n 93 if (!_adjacentEdges.ContainsKey(begin))n 94 {n 95 var edges = new List<Edge>();n 96 _adjacentEdges.Add(begin, edges);n 97 }n 98 n 99 _adjacentEdges[begin].Add(new Edge(begin, end, weight));n100 }n101 n102 public int FordFulkerson(int s, int t)n103 {n104 int u, v;n105 n106 // Create a residual graph and fill the residual graph withn107 // given capacities in the original graph as residual capacitiesn108 // in residual graphn109 int[,] residual = new int[VertexCount, VertexCount];n110 n111 // Residual graph where rGraph[i,j] indicates n112 // residual capacity of edge from i to j (if theren113 // is an edge. If rGraph[i,j] is 0, then there is not) n114 for (u = 0; u < VertexCount; u++)n115 for (v = 0; v < VertexCount; v++)n116 residual[u, v] = 0;n117 foreach (var edge in this.Edges)n118 {n119 residual[edge.Begin, edge.End] = edge.Weight;n120 }n121 n122 // This array is filled by BFS and to store pathn123 int[] parent = new int[VertexCount];n124 n125 // There is no flow initiallyn126 int maxFlow = 0;n127 n128 // Augment the flow while there is path from source to sinkn129 while (BFS(residual, s, t, parent))n130 {n131 // Find minimum residual capacity of the edhes along then132 // path filled by BFS. Or we can say find the maximum flown133 // through the path found.n134 int pathFlow = int.MaxValue;n135 for (v = t; v != s; v = parent[v])n136 {n137 u = parent[v];n138 pathFlow = pathFlow < residual[u, v]n139 ? pathFlow : residual[u, v];n140 }n141 n142 // update residual capacities of the edges and reverse edgesn143 // along the pathn144 for (v = t; v != s; v = parent[v])n145 {n146 u = parent[v];n147 residual[u, v] -= pathFlow;n148 residual[v, u] += pathFlow;n149 }n150 n151 // Add path flow to overall flown152 maxFlow += pathFlow;n153 }n154 n155 // Return the overall flown156 return maxFlow;n157 }n158 n159 // Returns true if there is a path from source s to sink t inn160 // residual graph. Also fills parent[] to store the path.n161 private bool BFS(int[,] residual, int s, int t, int[] parent)n162 {n163 bool[] visited = new bool[VertexCount];n164 for (int i = 0; i < visited.Length; i++)n165 {n166 visited[i] = false;n167 }n168 n169 Queue<int> q = new Queue<int>();n170 n171 visited[s] = true;n172 q.Enqueue(s);n173 parent[s] = -1;n174 n175 // standard BFS loopn176 while (q.Count > 0)n177 {n178 int u = q.Dequeue();n179 n180 for (int v = 0; v < VertexCount; v++)n181 {n182 if (!visited[v]n183 && residual[u, v] > 0)n184 {n185 q.Enqueue(v);n186 visited[v] = true;n187 parent[v] = u;n188 }n189 }n190 }n191 n192 // If we reached sink in BFS starting from source, n193 // then return true, else falsen194 return visited[t] == true;n195 }n196 }n197 }n198 }n

運行結果如下：