<p>from <a href="/ja/Dinic">Dinic</a>
最大流を求めるアルゴリズムの歴史</p>
<ul>
<li><a href="https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%95%E3%82%A1%E3%83%AB%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%B3%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0">フォード・ファルカーソンのアルゴリズム - Wikipedia</a><ul>
<li>1956</li>
<li>容量が無理数の場合、停止しない可能性がある</li>
<li>容量が整数の場合、最大フローをfとしてO(Ef)<ul>
<li>これは1ステップごとにフローが増加することによる</li>
<li>有理数の場合は適当に整数を掛ければ整数になる</li>
</ul>
</li>
</ul>
</li>
<li><a href="https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%89%E3%83%A2%E3%83%B3%E3%82%BA%E3%83%BB%E3%82%AB%E3%83%BC%E3%83%97%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0">エドモンズ・カープのアルゴリズム - Wikipedia</a><ul>
<li>1972</li>
<li>O(VE^2)<ul>
<li>フォード・ファルカーソンのアルゴリズムとほぼ同じ</li>
<li>スタートから最初に幅優先探索して距離を求めておく<ul>
<li>増加道の探索の際にスタートから遠ざかる方向にだけ探索する</li>
</ul>
</li>
<li><a href="https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm">Edmonds–Karp algorithm - Wikipedia</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="https://en.wikipedia.org/wiki/Dinic%27s_algorithm">Dinic&#39;s algorithm - Wikipedia</a><ul>
<li>1970</li>
<li>O(V^2E)</li>
<li>エドモンズ・カープのアルゴリズムとほぼ同じ<ul>
<li>追加の工夫がある</li>
<li>さらにO(VElogV)にすることもできる</li>
</ul>
</li>
</ul>
</li>
</ul>
