首页 > 代码库 > Ford-Fulkerson 最大流算法

Ford-Fulkerson 最大流算法

2024-11-23 18:39:39   203人阅读

流网络（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 03   while there exists an augmenting path p4     do augment flow f along p5   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 with107         // given capacities in the original graph as residual capacities108         // in residual graph109         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 there113         // 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 path123         int[] parent = new int[VertexCount];124 125         // There is no flow initially126         int maxFlow = 0;127 128         // Augment the flow while there is path from source to sink129         while (BFS(residual, s, t, parent))130         {131           // Find minimum residual capacity of the edhes along the132           // path filled by BFS. Or we can say find the maximum flow133           // 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 edges143           // along the path144           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 flow152           maxFlow += pathFlow;153         }154 155         // Return the overall flow156         return maxFlow;157       }158 159       // Returns true if there is a path from source ‘s‘ to sink ‘t‘ in160       // 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 loop176         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 false194         return visited[t] == true;195       }196     }197   }198 }

运行结果如下：

技术分享

参考资料

  • 广度优先搜索
  • 深度优先搜索
  • 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 发表自博客园，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。

Ford-Fulkerson 最大流算法


联系
我们