Форд-Фулкерсон не работает на этом графике

Question

Мой анализ алгоритма Ford-Fulkerson не подходит. Например, возьмем следующий график:

 _____>4___>_ 
    |   | 
0--->1---->3------6 
| |   | 
2--->5--------->--- 

Узел 0 источник, узел 6 является терминальным узлом, и ограничение каждое ребро является 1, за исключением того, края от узла 0 до ограничения 1 «s равно 2. Если поток идет от 0-> 1-> 3-> 6 и 0-> 1-> 4-> 6 и 0-> 2-> 5-> 6, поток графика равен 3. Однако, если поток начинается с 0-> 1, перейдем от 0-> 1-> 3-> 6 и 0-> 1-> 5-> 6, мы больше не можем перейти от 0-> 2-> 5-> 6, так как 5- > 6 уже занят. Поскольку ограничение 0-> 1 равно 2, мы можем начинать только с 0-> 1 дважды, поэтому поток графика равен 2. Очевидно, что максимальный возможный поток графика должен быть не 3, а 2. Будет ли Форд-Фулкерсон алгоритм обрабатывает эту проблему и всегда возвращает 3 в качестве ответа?

Answer 1

Да Ford-Fulkerson может. Всегда решать такие проблемы - это то, на что он предназначен.

Я думаю, что вам не хватает того, что при определении остаточного графика вам также нужно добавить задние края. Таким образом, после того, как происходит 0-> 1-> 3-> 6 и 0-> 1-> 5-> 6 остаточный график, на самом деле выглядит следующим образом:

   1   1 
      +-------> 4 ------+ 
      |     | 
     2 |  1  1 v 
    0 <------ 1 <----- 3 <----- 6 
    |  ^    | 
    | 1  | 1    | 1 
    +-------> 5 <---------------+ 

Следующим шагом Форд-Фулкерсон собирается принять это добавив маршрут 0-> 5-> 1-> 4-> 6, таким образом получив поток 3.

Answer 2

Это будет таймаут, когда maxFlow будет слишком высоким. (В худшем случае Ford fulkerson добавляет только 1 поток на каждом шаге)

Просто используйте BFS вместо DFS в ford fulkerson, и это станет Edmonds carp! Его слишком быстро и широко используется по сравнению с Ford-fulkerson.

Вы также можете проверить PFS (приоритетный первый поиск), который поясняется here.