Dinic

释义 Definition

Dinic 通常指 Dinic 算法（也常写作 Dinitz algorithm）：一种用于求解网络最大流（maximum flow）的经典算法，核心思想是反复构建分层图（level graph）并在其中寻找阻塞流（blocking flow），时间复杂度在实践与竞赛中表现优秀。

发音 Pronunciation

/ˈdɪnɪk/

例句 Examples

Dinic is fast enough for most max-flow problems in contests.
Dinic 算法在竞赛中对大多数最大流问题都足够快。

We used Dinic to compute the maximum flow on a large bipartite-matching instance by building a level graph and sending blocking flows repeatedly.
我们使用 Dinic 算法来计算一个大型二分匹配实例的最大流：先构建分层图，再反复增广阻塞流。

词源 Etymology

Dinic 来自该算法提出者的姓氏转写，常与 Dinitz（迪尼茨） 互见。该最大流算法由苏联/俄罗斯学者 Yefim (Chaim) Dinitz 于 1970 年左右提出，因此在不同文献与社区中会出现不同拼写（Dinic/Dinitz），但通常指同一类最大流方法。

相关词 Related Words

• Maximum Flow
• Flow Network
• Level Graph
• Blocking Flow
• Augmenting Path
• Edmonds-Karp
• Push-Relabel
• Bipartite Matching
• Capacity
• Residual Graph

文学与著作出处 Literary Works

• 《Introduction to Algorithms》（CLRS，《算法导论》）：在网络流相关章节中讨论最大流思想与典型算法体系，常提及与 Dinic/Dinitz 同类的方法框架。
• 《Competitive Programming》（Steven Halim 等，《算法竞赛入门/竞赛程序设计》系列）：常以 Dinic 作为竞赛中最大流的标准实现之一。
• 《Algorithms》（Dasgupta, Papadimitriou, Vazirani，《算法》）：在图算法与网络流主题下介绍最大流问题与经典解法脉络，涉及 Dinitz/Dinic 相关思想。