网络流伪代码模板(Edmonds-Karp/Dinic/ISAP)

• 2018-01-14
• 0
• 0

Preface:

由于伪代码能较简洁地呈现算法的主要实现过程，有助于理解，我在本文中写了 Edmonds-Karp / Dinic / ISAP 的伪代码模板，希望对大家有所帮助。

以下三种算法均基于 Ford-Fulkerson 方法（增广路方法）

【Edmonds-Karp 算法】
时间复杂度: O(VE²)
空间复杂度: O(V+E)

核心步骤:

1. 输入一个零流图，建立残量网络。
2. 使用 BFS 在残量网络中寻找增广路。
3. 若存在增广路，则用增流更新残量网络，将其计入总流量，并转步骤 2。否则转步骤 4。
4. 输出总流量，即为最大流。

ALGORITHM Edmonds-Karp(G, S, T): [Time Complexity O(V*E^2)]
	maxflow = 0
	repeat
		q = new QUEUE
		q.push(S)
		prev = new *EDGE[G.size]  // The previous edge of each point
		while not q.empty()
			u = q.front()
			q.pop()
			for each EDGE e from u
				if prev[e.t] == null and e.t ≠ s and e.cap > e.flow
					prev[e.t] = e
					q.push(e.t)
		if prev[T] ≠ null  // Find an Augmenting Path
			dflow = +∞
			for (e = prev[T]; e ≠ null; e = prev[e.s])
				dflow = min(dflow, e.cap - e.flow)  // Get the increased flow
			for (e = prev[T]; e ≠ null; e = prev[e.s])
				e.flow += dflow
				e.rev.flow -= dflow
			maxflow += dflow  // Update the flow
	until prev[T] == null  // No more Augmenting Path
	return maxflow

【Dinic 算法】
时间复杂度: O(V²E)
空间复杂度: O(V+E)

核心步骤:

1. 输入零流图，建立残量网络。
2. 用 BFS 将残量网络分层，其中源点为第 0 层，若分层图中汇点不可达，则转步骤 5。
3. 用 DFS 在分层图中寻找增广路，确保路径上的点的层次递增。
4. 若存在增广路，则在 DFS 回溯时用增流更新残量网络，退出后将其计入总流量，并转步骤 3。否则转步骤 2。
5. 输出总流量，即为最大流。

优化:  当前弧优化 (Current Arc Optimization)。

ALGORITHM Dinic(G, S, T): [Time Complexity O(V^2*E)]
	BFS():
		q = new QUEUE
		q.push(S)
		level = new INT[G.size]  // Record the BFS level
		while not q.empty()
			u = q.front()
			q.pop()
			for each EDGE e from u
				if e.cap > e.flow and level[e.t] == null  // Only augmentable edges are counted
					level[e.t] = level[u] + 1  // Mark the vertice according to the BFS level
					q.push(e.t)
		return level[e.t] ≠ null  // Find whether the sink point is reachable through augmentable edges
	
	DFS(u, curflow):
		if u == T
			return curflow  // Find an Augmenting Path
		for each EDGE e from u, skipping those before arc[u]  // ~~~ Current Arc Optimization ~~~
			arc[u] = e
			if level[e.t] == level[u] + 1 and e.cap > e.flow  // Only the next level are available
				dflow = DFS(e.t, min(curflow, e.cap - e.flow))
				if dflow > 0
					e.flow += dflow
					e.rev.flow -= dflow
					return dflow  // Update the flow
		return 0
	
	maxflow = 0
	while BFS()
		arc = the first EDGE from each point  // Initialize Current Arcs after each BFS
		flow = DFS(S, +∞)
		while flow > 0
			maxflow += flow  // Update the flow
			flow = DFS(S, +∞)  // Several Augmenting Paths may be found after only one BFS
	return maxflow

Dinic 算法的另一种写法，在一次 DFS 中进行多次增广，理论上效率略优于上述写法:

ALGORITHM Dinic(G, S, T): [Time Complexity O(V^2*E)]
	BFS():
		q = new QUEUE
		q.push(S)
		level = new INT[G.size]  // Record the BFS level
		while not q.empty()
			u = q.front()
			q.pop()
			for each EDGE e from u
				if e.cap > e.flow and level[e.t] == null  // Only augmentable edges are counted
					level[e.t] = level[u] + 1  // Mark the vertice according to the BFS level
					q.push(e.t)
		return level[e.t] ≠ null  // Find whether the sink point is reachable through augmentable edges
	
	DFS(u, curflow):
		if u == T
			return curflow  // Find an Augmenting Path
		remflow = curflow
		for each EDGE e from u, skipping those before arc[u]  // ~~~ Current Arc Optimization ~~~
			arc[u] = e
			if level[e.t] == level[u] + 1 and e.cap > e.flow  // Only the next level are available
				dflow = DFS(e.t, min(remflow, e.cap - e.flow))  // Find several Augmenting Paths using the remaining flow
				if dflow > 0
					e.flow += dflow
					e.rev.flow -= dflow
					remflow -= dflow  // Update the flow
		return curflow - remflow
	
	maxflow = 0
	while BFS()
		arc = the first EDGE from each point  // Initialize Current Arcs after each BFS
		maxflow += DFS(S, +∞)  // Update the flow
	return maxflow

【ISAP 算法】
时间复杂度: O(V²E)
空间复杂度: O(V+E)

核心步骤:

1. 输入零流图，建立残量网络。
2. 用 BFS 将残量网络分层，其中汇点为第 0 层。
3. 若源点的层次标记小于顶点数，则转步骤 4。否则转步骤 7。
4. 从源点开始，每次尝试走低一个层次的顶点，进行步骤 5 和 步骤 6 的判断，然后转步骤 3。
5. 若无法继续走，则将当前点的层次重标记为所有邻节点中最小层次加 1，并回溯到前驱节点。
6. 若到达汇点，则找到一条增广路。用增流更新残量网络，将其计入总流量，然后重新从源点开始尝试即可。
7. 输出总流量，即为最大流。

优化:  当前弧优化 (Current Arc Optimization)，间隙优化 (Gap Optimization)。

ALGORITHM ISAP(G, S, T): [Time Complexity O(V^2*E)]
	BFS():
		q = new QUEUE
		q.push(T)
		dis = new INT[G.size]  // Record the distance (i.e. the minimum number of steps) to the sink point 
		while not q.empty()
			u = q.front()
			q.pop()
			for each EDGE e from u
				if e.cap > e.flow and dis[e.t] == null  // Only augmentable edges are counted
					dis[e.t] = dis[u] + 1  // Mark the distance
					q.push(e.t)
	
	maxflow = 0
	BFS()  // Initialize for only 1 time, then the distance will be remarked during the finding of Augmenting Paths
	num = the number of points of each level  // Record this for Gap Optimization
	arc = the first EDGE from each point  // Record this for Current Arc Optimization
	u = S
	while dis[S] < G.size
		if u == T
			dflow = +∞
			for (e = prev[T]; e ≠ null; e = prev[e.s])
				dflow = min(dflow, e.cap - e.flow)  // Get the increased flow
			for (e = prev[T]; e ≠ null; e = prev[e.s])
				e.flow += dflow
				e.rev.flow -= dflow
			maxflow += dflow  // Update the flow
			u = S  // Try to find another Augmenting Path
		retreat = true
		for each EDGE e from u, skipping those before arc[u]  // ~~~ Current Arc Optimization ~~~
			if dis[u] == dis[e.t] + 1 and e.cap > e.flow  // Only the next level are available
				arc[u] = prev[u] = e
				retreat = false  // No need to retreat if it has edges to the next-level point
				u = e.t  // Go forth
				break
		if retreat  // This point has no edge to the next-level point 
			newdis = G.size - 1
			for each EDGE e from u
				if e.cap > e.flow
					newdis = min(newdis, dis[e.t])  // Find the minimum distance of neighbor points
			num[dis[u]]--
			if num[dis[u]] == 0
				break  // ~~~ Gap Optimization ~~~ If there is a level with no point, there is no more Augmenting Path
			dis[u] = newdis + 1  // Set the distance to the minimum distance of neighbor points plus 1
			num[dis[u]]++
			arc[u] = the first EDGE from u  // Reset the Current Arc of u to the first edge
			if u ≠ S
				u = prev[u].s  // Backdate
	return maxflow