屈婉玲《算法设计与分析》第2版第7章网络流算法学习笔记。
Dinic有效算法同样用来求最大流，相当于FF算法的改进。
FF算法参考：网络流算法学习笔记——最大流问题基本概念和Ford-Fulkerson方法（标号法C++实现）
改进之处有：
第1点显然能提高效率，但第2点为什么要找最短路径呢？看《算法导论》的一个FF算法的例子。
初始为0流的网络，找到一条增广路径：
更新残留网络，再找增广路径：
更新残留网络：
在这种情况下，每次仅增加1个单位的总流量，共要执行2,000,000次运算。
dinic算法能确保不发生这种情况。
初始网络N，及当前可行流f：
辅助网络、辅助容量：N(f)、ac
设容量网络N，f是一个可行流，记其辅助网络为N(f)；屈婉玲版《算法设计与分析》对残留网络的别称。
辅助容量是辅助网络中重新定义的容量 ：
即前向边还能压入多少流量，后向边还能退回多少流量。
分层辅助网络：AN(f)
删除辅助网络中部分非最短路径的辅助网络。用广度优先搜索N(f)，标记每个节点的层号（图b方框里标注），把从高层到低层的边，及层数大于等于t的顶点删掉。
流通量：th(i)
AN(f)中所有以顶点i为终点的边的容量和，与所有以i为始点的容量和中的最小者。即顶点i所能承载的最大流量。规定以s为终点和以t为始点的边的容量为+∞。
接下来，循环执行下面的步骤2、3。
流通量为0的顶点及关联的边都可以删去，出现新的流通量0的顶点继续删：
至此，网络简化了不少，准备工作完成了。
构造好AN(f)后，尽可能多的找出s到t的最短路径并分配流量：
安排完毕后，重复步骤2，AN(f)变成了下图；重复步骤3安排流量：
再重复步骤2，发现此时s、t的流通量都变为了0（下图所有顶点流通量都是0），跳出循环：
至此，把以上找到的流叠加起来，就找到了AN(f)的一个极大流g1，如下：
将极大流叠加到原来的流f上，得到新的N和f2：
至此第一个过程结束。回到步骤1，重复执行上述过程，构造AN(f)并寻找其极大流：
下一组，构造AN(f)时发现没有从s到t的通路，计算结束：
屈婉玲《算法设计与分析》第2版中的伪代码如下：
1. f ← 0 //取零流作为初始可行流
2. 构造AN(f) //bfs遍历
3. if AN(f)中不存在从s到t的路径 then return f //计算结束
4. g ← 0
5. if AN(f)中存在th(i)=0 then
6. if i=s or i=t then goto 15
7. else 删去i及其关联的边
8. 找到流通量最小的顶点k，从k开始将th(k)个单位的流量向后送到t，向前推到s，并将它们加到g上
9. 删去k及其关联的边
10. for <i, j> ∈ AE(f) do
11. if g(i, j)=ac(i, j) then
12. 删去<i, j>
13. else ac(i, j)←ac(i, j) - g(i, j)
14. goto 5
15. f ← f + g
16. goto 2
唯一没明确方法的是第8步，如何安排流量？可以采用dfs的方法，从k分别向后、向前dfs。
下面分析复杂度。AN(f)中s-t的距离每个阶段至少增加1（每次都找最短的），所以至多有n个阶段。每个阶段中：
所以总工作量为O(n3)。
下面是简洁的教程邻接表版C++实现，来自：Dinic’s algorithm for Maximum Flow
#include<bits/stdc++.h>
using namespace std;
// A structure to represent a edge between
// two vertex
struct Edge
{
int v ; // Vertex v (or "to" vertex)
// of a directed edge u-v. "From"
// vertex u can be obtained using
// index in adjacent array.
int flow ; // flow of data in edge
int C; // capacity
int rev ; // To store index of reverse
// edge in adjacency list so that
// we can quickly find it.
};
// Residual Graph
class Graph
{
int V; // number of vertex
int *level ; // stores level of a node
vector< Edge > *adj;
public :
Graph(int V)
{
adj = new vector<Edge>[V];
this->V = V;
level = new int[V];
}
// add edge to the graph
void addEdge(int u, int v, int C)
{
// Forward edge : 0 flow and C capacity
Edge a{v, 0, C, adj[v].size()};
// Back edge : 0 flow and 0 capacity
Edge b{u, 0, 0, adj[u].size()};
adj[u].push_back(a);
adj[v].push_back(b); // reverse edge
}
bool BFS(int s, int t);
int sendFlow(int s, int flow, int t, int ptr[]);
int DinicMaxflow(int s, int t);
};
// Finds if more flow can be sent from s to t.
// Also assigns levels to nodes.
bool Graph::BFS(int s, int t)
{
for (int i = 0 ; i < V ; i++)
level[i] = -1;
level[s] = 0; // Level of source vertex
// Create a queue, enqueue source vertex
// and mark source vertex as visited here
// level[] array works as visited array also.
list< int > q;
q.push_back(s);
vector<Edge>::iterator i ;
while (!q.empty())
{
int u = q.front();
q.pop_front();
for (i = adj[u].begin(); i != adj[u].end(); i++)
{
Edge &e = *i;
if (level[e.v] < 0 && e.flow < e.C)
{
// Level of current vertex is,
// level of parent + 1
level[e.v] = level[u] + 1;
q.push_back(e.v);
}
}
}
// IF we can not reach to the sink we
// return false else true
return level[t] < 0 ? false : true ;
}
// A DFS based function to send flow after BFS has
// figured out that there is a possible flow and
// constructed levels. This function called multiple
// times for a single call of BFS.
// flow : Current flow send by parent function call
// start[] : To keep track of next edge to be explored.
// start[i] stores count of edges explored
// from i.
// u : Current vertex
// t : Sink
int Graph::sendFlow(int u, int flow, int t, int start[])
{
// Sink reached
if (u == t)
return flow;
// Traverse all adjacent edges one -by - one.
for ( ; start[u] < adj[u].size(); start[u]++)
{
// Pick next edge from adjacency list of u
Edge &e = adj[u][start[u]];
if (level[e.v] == level[u]+1 && e.flow < e.C)
{
// find minimum flow from u to t
int curr_flow = min(flow, e.C - e.flow);
int temp_flow = sendFlow(e.v, curr_flow, t, start);
// flow is greater than zero
if (temp_flow > 0)
{
// add flow to current edge
e.flow += temp_flow;
// subtract flow from reverse edge
// of current edge
adj[e.v][e.rev].flow -= temp_flow;
return temp_flow;
}
}
}
return 0;
}
// Returns maximum flow in graph
int Graph::DinicMaxflow(int s, int t)
{
// Corner case
if (s == t)
return -1;
int total = 0; // Initialize result
// Augment the flow while there is path
// from source to sink
while (BFS(s, t) == true)
{
// store how many edges are visited
// from V { 0 to V }
int *start = new int[V+1];
// while flow is not zero in graph from S to D
while (int flow = sendFlow(s, INT_MAX, t, start))
// Add path flow to overall flow
total += flow;
}
// return maximum flow
return total;
}
// Driver program to test above functions
int main()
{
Graph g(6);
g.addEdge(0, 1, 16 );
g.addEdge(0, 2, 13 );
g.addEdge(1, 2, 10 );
g.addEdge(1, 3, 12 );
g.addEdge(2, 1, 4 );
g.addEdge(2, 4, 14);
g.addEdge(3, 2, 9 );
g.addEdge(3, 5, 20 );
g.addEdge(4, 3, 7 );
g.addEdge(4, 5, 4);
// next exmp
/*g.addEdge(0, 1, 3 );
g.addEdge(0, 2, 7 ) ;
g.addEdge(1, 3, 9);
g.addEdge(1, 4, 9 );
g.addEdge(2, 1, 9 );
g.addEdge(2, 4, 9);
g.addEdge(2, 5, 4);
g.addEdge(3, 5, 3);
g.addEdge(4, 5, 7 );
g.addEdge(0, 4, 10);
// next exp
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 10);
g.addEdge(1, 3, 4 );
g.addEdge(1, 4, 8 );
g.addEdge(1, 2, 2 );
g.addEdge(2, 4, 9 );
g.addEdge(3, 5, 10 );
g.addEdge(4, 3, 6 );
g.addEdge(4, 5, 10 ); */
cout << "Maximum flow " << g.DinicMaxflow(0, 5);
return 0;
}
输出结果:
Maximum flow 23