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)
2   initialize flow f to 0
3   while there exists an augmenting path p
4     do augment flow f along p
5   return f

上述伪码实现的时间复杂度为 O(max_flow * E)。

C# 代码实现如下:

复制代码
  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 
  5 namespace GraphAlgorithmTesting
  6 {
  7   class Program
  8   {
  9     static void Main(string[] args)
 10     {
 11       Graph g = new Graph(6);
 12       g.AddEdge(0, 1, 16);
 13       g.AddEdge(0, 2, 13);
 14       g.AddEdge(1, 2, 10);
 15       g.AddEdge(1, 3, 12);
 16       g.AddEdge(2, 1, 4);
 17       g.AddEdge(2, 4, 14);
 18       g.AddEdge(3, 2, 9);
 19       g.AddEdge(3, 5, 20);
 20       g.AddEdge(4, 3, 7);
 21       g.AddEdge(4, 5, 4);
 22 
 23       Console.WriteLine();
 24       Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);
 25       Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);
 26       Console.WriteLine();
 27 
 28       int maxFlow = g.FordFulkerson(0, 5);
 29       Console.WriteLine("The Max Flow is : {0}", maxFlow);
 30 
 31       Console.ReadKey();
 32     }
 33 
 34     class Edge
 35     {
 36       public Edge(int begin, int end, int weight)
 37       {
 38         this.Begin = begin;
 39         this.End = end;
 40         this.Weight = weight;
 41       }
 42 
 43       public int Begin { get; private set; }
 44       public int End { get; private set; }
 45       public int Weight { get; private set; }
 46 
 47       public override string ToString()
 48       {
 49         return string.Format(
 50           "Begin[{0}], End[{1}], Weight[{2}]",
 51           Begin, End, Weight);
 52       }
 53     }
 54 
 55     class Graph
 56     {
 57       private Dictionary<int, List<Edge>> _adjacentEdges
 58         = new Dictionary<int, List<Edge>>();
 59 
 60       public Graph(int vertexCount)
 61       {
 62         this.VertexCount = vertexCount;
 63       }
 64 
 65       public int VertexCount { get; private set; }
 66 
 67       public IEnumerable<int> Vertices
 68       {
 69         get
 70         {
 71           return _adjacentEdges.Keys;
 72         }
 73       }
 74 
 75       public IEnumerable<Edge> Edges
 76       {
 77         get
 78         {
 79           return _adjacentEdges.Values.SelectMany(e => e);
 80         }
 81       }
 82 
 83       public int EdgeCount
 84       {
 85         get
 86         {
 87           return this.Edges.Count();
 88         }
 89       }
 90 
 91       public void AddEdge(int begin, int end, int weight)
 92       {
 93         if (!_adjacentEdges.ContainsKey(begin))
 94         {
 95           var edges = new List<Edge>();
 96           _adjacentEdges.Add(begin, edges);
 97         }
 98 
 99         _adjacentEdges[begin].Add(new Edge(begin, end, weight));
100       }
101 
102       public int FordFulkerson(int s, int t)
103       {
104         int u, v;
105 
106         // Create a residual graph and fill the residual graph with
107         // given capacities in the original graph as residual capacities
108         // in residual graph
109         int[,] residual = new int[VertexCount, VertexCount];
110 
111         // Residual graph where rGraph[i,j] indicates 
112         // residual capacity of edge from i to j (if there
113         // is an edge. If rGraph[i,j] is 0, then there is not) 
114         for (u = 0; u < VertexCount; u++)
115           for (v = 0; v < VertexCount; v++)
116             residual[u, v] = 0;
117         foreach (var edge in this.Edges)
118         {
119           residual[edge.Begin, edge.End] = edge.Weight;
120         }
121 
122         // This array is filled by BFS and to store path
123         int[] parent = new int[VertexCount];
124 
125         // There is no flow initially
126         int maxFlow = 0;
127 
128         // Augment the flow while there is path from source to sink
129         while (BFS(residual, s, t, parent))
130         {
131           // Find minimum residual capacity of the edhes along the
132           // path filled by BFS. Or we can say find the maximum flow
133           // through the path found.
134           int pathFlow = int.MaxValue;
135           for (v = t; v != s; v = parent[v])
136           {
137             u = parent[v];
138             pathFlow = pathFlow < residual[u, v]
139               ? pathFlow : residual[u, v];
140           }
141 
142           // update residual capacities of the edges and reverse edges
143           // along the path
144           for (v = t; v != s; v = parent[v])
145           {
146             u = parent[v];
147             residual[u, v] -= pathFlow;
148             residual[v, u] += pathFlow;
149           }
150 
151           // Add path flow to overall flow
152           maxFlow += pathFlow;
153         }
154 
155         // Return the overall flow
156         return maxFlow;
157       }
158 
159       // Returns true if there is a path from source 's' to sink 't' in
160       // residual graph. Also fills parent[] to store the path.
161       private bool BFS(int[,] residual, int s, int t, int[] parent)
162       {
163         bool[] visited = new bool[VertexCount];
164         for (int i = 0; i < visited.Length; i++)
165         {
166           visited[i] = false;
167         }
168 
169         Queue<int> q = new Queue<int>();
170 
171         visited[s] = true;
172         q.Enqueue(s);
173         parent[s] = -1;
174 
175         // standard BFS loop
176         while (q.Count > 0)
177         {
178           int u = q.Dequeue();
179 
180           for (int v = 0; v < VertexCount; v++)
181           {
182             if (!visited[v]
183               && residual[u, v] > 0)
184             {
185               q.Enqueue(v);
186               visited[v] = true;
187               parent[v] = u;
188             }
189           }
190         }
191 
192         // If we reached sink in BFS starting from source, 
193         // then return true, else false
194         return visited[t] == true;
195       }
196     }
197   }
198 }
复制代码

运行结果如下:

参考资料








本文转自匠心十年博客园博客,原文链接:http://www.cnblogs.com/gaochundong/p/ford_fulkerson_maximum_flow_algorithm.html,如需转载请自行联系原作者

目录
相关文章
|
算法
计算机基础问题,最大流问题获突破性进展:新算法「快得离谱」
计算机基础问题,最大流问题获突破性进展:新算法「快得离谱」
|
算法 Java
关于最大流的EdmondsKarp算法详解
最近大三学生让我去讲课,我就恶补了最大流算法,笔者认为最重要的是让学弟学妹们入门,知道算法怎么来的?为什么是这样?理解的话提出自己的改进,然后再看看Dinic、SAP和ISAP算法….. 一、概念引入       首先要先清楚最大流的含义,就是说从源点到经过的所有路径的最终到达汇点的所有流量和。
1298 0
|
算法
GraphCuts算法解析,Graphcuts算法求最大流,最小割实例
   图割论文大合集下载: http://download.csdn.net/detail/wangyaninglm/8292305   代码: /* graph.h */ /* Vladimir Kolmogorov (vnk@cs.
1199 0
|
机器学习/深度学习 算法 JavaScript
【算法导论】最大流算法
最大流问题就是在容量容许的条件下,从源点到汇点所能通过的最大流量。 1 流网络        网络流G=(v, E)是一个有向图,其中每条边(u, v)均有一个非负的容量值,记为c(u, v) ≧ 0。
1158 0
|
5天前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。
|
2天前
|
算法 数据挖掘
基于粒子群优化算法的图象聚类识别matlab仿真
该程序基于粒子群优化(PSO)算法实现图像聚类识别,能识别0~9的数字图片。在MATLAB2017B环境下运行,通过特征提取、PSO优化找到最佳聚类中心,提高识别准确性。PSO模拟鸟群捕食行为,通过粒子间的协作优化搜索过程。程序包括图片读取、特征提取、聚类分析及结果展示等步骤,实现了高效的图像识别。
|
1月前
|
算法 BI Serverless
基于鱼群算法的散热片形状优化matlab仿真
本研究利用浴盆曲线模拟空隙外形,并通过鱼群算法(FSA)优化浴盆曲线参数,以获得最佳孔隙度值及对应的R值。FSA通过模拟鱼群的聚群、避障和觅食行为,实现高效全局搜索。具体步骤包括初始化鱼群、计算适应度值、更新位置及判断终止条件。最终确定散热片的最佳形状参数。仿真结果显示该方法能显著提高优化效率。相关代码使用MATLAB 2022a实现。
|
1月前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
下一篇
无影云桌面