Алгоритм отмены цикла

Алгоритм отмены цикла

Отмена цикла алгоритм начинается с разрешения максимальный расход. Затем итеративно алгоритм ищет цикл с отрицательной стоимостью (отрицательная стоимость, если ребро берется в направлении, противоположном потоку) и увеличивает поток на этом цикле. Когда отрицательных циклов больше нет, алгоритм завершает работу.

Пример :

алгоритм отрицательного цикла отмены цикла

давайте построим это график разрыв и искать отрицательный цикл:

алгоритм отрицательного цикла отмены цикла

Цикл 4-2-3-4 имеет стоимость -3 + 1 + 1 = -1, мы можем насытить его потоком 2.

Аналогично циклу 4-2-1-3-4 со стоимостью -3-2+2+1=-2 мы можем насытить его потоком 1.

Отрицательного цикла больше нет, алгоритм завершается.

Делиться
ru_RURU
%d такие блоггеры, как: