Изменения

Этот алгоритм работает в предположении, что все пропускные способности ребер целые. Пусть есть граф <tex>G</tex>, <tex>\forall (u,v)\in E\colon u_{(u,v)}\in\mathbb N</tex>. Суть алгоритма в нахождении сначала путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток. Пусть <tex>U</tex> - максимальная пропускная способность. Введем параметр <tex>\Delta</tex>. Это большое число, к примеру, равное <tex>U= 2^{\lfloor\log_2U\rfloor}</tex>. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше <tex>\Delta</tex> и увеличивать поток вдоль этих путей. В конце шага будем уменьшать <tex>\Delta</tex> в два раза, и на следующем шаге будем искать увеличивающий путь с новым <tex>\Delta</tex>. При <tex>\Delta == 1</tex> алгоритм масштабирования идентичен [[Алоритм_Эдмондса-Карпа | алгоритму Эдмондса - Карпа]], поэтому алгоритм масштабирования корректен.