# 迪尼茨算法

（重定向自Dinic算法

## 定义

${\displaystyle G=((V,E),c,s,t)}$为一个每条边的容量为${\displaystyle c(u,v)}$，流为${\displaystyle f(u,v)}$的网络。

1. 如果${\displaystyle (u,v)\in E}$,
${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$
${\displaystyle c_{f}(v,u)=f(u,v)}$
2. 否则${\displaystyle c_{f}(u,v)=0}$

${\displaystyle E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}}$.

${\displaystyle E_{L}=\{(u,v)\in E_{f}:\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$.

## 算法

1. 对每条边${\displaystyle e\in E}$，设${\displaystyle f(e)=0}$
2. 在图${\displaystyle G}$的残留网络${\displaystyle G_{f}}$中计算${\displaystyle G_{L}}$。如果${\displaystyle \operatorname {dist} (t)=\infty }$停止程序并输出${\displaystyle f}$.
3. ${\displaystyle G_{L}}$找到一条阻塞流${\displaystyle f\;'}$
4. ${\displaystyle \ f}$增加${\displaystyle f\;'}$并返回第二步。

## 参考文献

1. ^ Yefim Dinitz. Algorithm for solution of a problem of maximum flow in a network with power estimation (PDF). Doklady Akademii nauk SSSR. 1970, 11: 1277–1280 [2016-08-04]. （原始内容存档 (PDF)于2016-08-22）.
2. ^ Ilan Kadar; Sivan Albagli. Dinitz's algorithm for finding a maximum flow in a network. 2009-11-27 [2016-08-04]. （原始内容存档于2016-06-24）.
3. ^ Yefim Dinitz. Dinitz's Algorithm: The Original Version and Even's Version (PDF). [2016-08-04]. （原始内容存档 (PDF)于2016-08-20）.
4. ^ Even, Shimon; Tarjan, R. Endre. Network Flow and Testing Graph Connectivity. SIAM Journal on Computing. 1975, 4 (4): 507–518. ISSN 0097-5397. doi:10.1137/0204043.
5. ^ Tarjan 1983，第102頁.
• Tarjan, R. E. Data structures and network algorithms. 1983.