По аналогии с анализом алгоритма Эдмондса-Карпа, мы получаем такую оценку: O (N M) * T (N, M), где T (N, M) - время, необходимое для нахождения кратчайшего пути в графе с N вершинами и M рёбрами.
Нельзя ли поподробнее, как получается эта оценка? В анализе Эдмондса-Карпа существенно, что мы делаем bfs, т.е., что все "стоимости" единичные. Да и в книжке "Ahuja, Magnanti, Orlin. Network flows" приводится оценка O(N U T(N, M)), где U - максимальная пропускная способность.