Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е. <tex>d'[t] > d[t]</tex>, где <tex>d'[t]</tex> — значение, полученное на следующей фазе алгоритма.
|proof=
От Проведём доказательство от противного. Рассмотрим кратчайший путь Пусть длина кратчайшего пути из истока в сток; по предположению, его длина должна сохраниться останется неизменнойпосле очередной фазы алгоритма. Однако Тогда остаточная сеть на следующей фазе содержит будет содержать только рёбра остаточной сети перед выполнением текущей данной фазы, либо обратные к ним. Таким образомИз этого получаем, пришли к противоречию: что нашёлся <tex>s \leadsto t</tex> путь, который не содержит насыщенных рёбер и имеет ту же длину, что и кратчайший путь. Этот Но этот путь должен был быть «заблокирован» блокирующим потоком, чего не произошло, в чём и заключается . Получили противоречие, что и требовалось доказать. Значит длина изменилась.
}}
Поскольку длина кратчайшего <tex>s \leadsto t</tex> пути не может превосходить <tex>n - 1</tex>, то, следовательно, алгоритм Диница совершает не более <tex>n - 1</tex> фазы.
