65
правок
Изменения
→Псевдокод
<tex>\Delta\leftarrow 2^{\lfloor\log_2U\rfloor}</tex>
'''while''' <tex>\Delta>0</tex>
'''do''' '''while''' в <tex>G_f</tex> существует <tex>s-t</tex> путь с пропускной способностью большей <tex>\Delta</tex> '''do''' <tex>P\leftarrow</tex> путь с пропускной способностью большей <tex>\Delta</tex> <tex>\delta\leftarrow\min\{c_{ij}\colon(i,j)\in P\}</tex> увеличить поток по ребрам <tex>P</tex> на <tex>\delta</tex> обновить <tex>G_f</tex> <tex>f\leftarrow f+\delta</tex> <tex>\Delta\leftarrow\Delta/2</tex> '''return''' f
== Литература ==
* [http://www.csd.uwo.ca/~yuri/Papers/iccv07_cap_scaling.pdf ''Olivier Juan, Yuri Boikov'': Capacity Scaling for Graph Cuts in Vision]
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited Algorithm Tutorials. Maximum Flow: Augmenting Path Algorithms Comparison]
