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

  • 2018-01-14
  • 0
  • 0

Preface:

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

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

【Edmonds-Karp 算法】
时间复杂度: O(VE2)
空间复杂度: 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(V2E)
空间复杂度: 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(V2E)
空间复杂度: 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

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai