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

• 2018-01-14
• 0
• 0

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

【Edmonds-Karp 算法】

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 算法】

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

```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 算法】

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

```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
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai