5.2. Алгоритм, основанный на цепи наименьшей стоимости

Алгоритм из разд. 5.1 начинает работу с произвольного потока со значением после чего происходит постепенное улучшение потока до тех пор, пока не будет получен поток минимальной стоимости. В терминологии математического программирования такой алгоритм следовало бы назвать основным алгоритмом, так как его первая цель состоит в получении допустимого потока, а затем поток улучшается с сохранением допустимости. Альтернативным подходом является двойственный метод, в котором для решения этой задачи начинают с построения потока с минимальной стоимостью, имеющего некоторое значение а затем добавляют в граф некоторый дополнительный поток, чтобы получить новый поток с минимальной стоимостью, имеющий значение пока не будет построен поток с минимальной стоимостью со значением В отношении этого метода следует

заметить, что начальный поток минимальной стоимости всегда имеется, так как нулевой поток является потоком минимальной стоимости со значением 0.

Алгоритм, который мы собираемся описать, основан на вычислении кратчайшей цепи и следующей теореме.

Теорема 6. Если поток минимальной стоимости в графе со значением и кратчайшая цепь (наименьшей стоимости) от в инкрементальном графе то является потоком минимальной стоимости со значением

Доказательство теоремы очень просто — надо показать, что если не содержит никакого цикла отрицательной стоимости, то также не содержит таких циклов. После этого все следует непосредственно из теоремы 5.

5.2.1. Описание алгоритма

Шаг 1. Начать с нулевых потоков на дугах и с потока, имеющего нулевое значение.

Шаг 2. Построить инкрементальный граф как это описано в разд. 2.3, и взять следующие стоимости дуг:

Шаг 3. Найти в графе кратчайшую цепь от вершины к вершине

Шаг 4. Найти наибольшую величину того потока, который можно послать вдоль не изменяя структуру графа Величина равна

Шаг 5. (I) Если значение потока меньше, чем требуемая величина произвести замену и вернуться к шагу 2.

(II) Если значение потока равно у, остановиться. является требуемым потоком минимальной стоимости.

(III) Если значение потока остановиться. Требуемым потоком минимальной стоимости будет

Здесь важно отметить, что граф на шаге 2 содержит как дуги положительной стоимости, так и отрицательной, и поэтому алгоритм кратчайшей цепи, используемый на шаге 3, не может быть алгоритмом Дейкстры, а должен быть (менее эффективным)

алгоритмом, описанным в разд. 2.2.1 гл. 8. Однако Хаувер, Эдмондс и Карп предложили недавно метод, позволяющий обойти вышеуказанную трудность и использовать более эффективные алгоритмы кратчайшей цепи.

5.2.2. Пример.

Снова вычислим поток минимальной стоимости со значением 20 для графа, изображенного на рис. 11.13. Вначале берем Инкрементальный граф изображен на рис. 11.13. Кратчайшей цепью в графе будет со значением , а оказывается равным 12.

Поток переходит в Кратчайшей цепью в соответствующем инкрементальном графе будет стоимостью равным 4.

Поток становится равным Кратчайшей цепью в будет со стоимостью

Поток становится равным Кратчайшей цепью в будет со стоимостью 31, и вдоль этой цепи можно послать 3 оставшиеся единицы потока для получения потока минимальной стоимости, изображенного на рис.