Здраствуйте.

Я нашел описание min cost max flow, где описан процесс выдачи потенциалов: http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/min-cost-max-flow-2009/algorithm

Там не доказывается, что выбор потенциалов описанных образом позволит избежать появления ребер отрицательного веса.

Пусть у нас такая остаточная сеть. Вершина 4 -исток. Вершина 5 — сток:

Найдем кратчайший путь веса 1 4->0->2->5 и протолкнем через него одну единицу потока. Получим такую остаточную сеть:

Найдем такой кратчайший по весу путь:

Он действительно кратчайший

4->1 вес: 0+0-0=0

1->2 вес: 1+0-1=0

2->0 вес: -1+1-0=0

0->3 вес: 1+0-0=1

3->5 вес:0+0-1=-1 (Ребро с отрицательным весом)

Т.к. появилось ребро отрицательного веса, гарантий, что Дейкстра сработает нет. Я неправильно понял описанный по ссылке алгоритм, или он неверен?