Продолжить Ford-Fulkelson

Question

Я пытаюсь изучить метод Ford-Fulkerson. Я составил пример для практики, и в какой-то момент я не могу продолжать увеличивать поток, но я знаю, что поток может быть выше.

Прежде всего, я увеличивается путь s -> 1 -> 2 -> t. И теперь я не могу найти никакого пути для увеличения потока. Я знаю, что если бы я сначала взял путь a -> 1 -> 5 -> 6 -> t, я мог бы увеличить путь s -> 3 -> 4 -> 2 -> t, но если бы мне пришлось его реализовать, я бы не знал, как это сделать.

Что я делаю неправильно?

Answer 1

Я понял. Я не знал, что можно использовать края в направлении, противоположном стрелке.

Таким образом, мы можем пройти путь s -> 3 -> 4 -> 2 -> 1 -> 5 -> 6 -> t.

Тогда мы получим ожидаемый результат.