Почему необходимо учитывать задние края в максимальном потоке Edmonds-Karp?

Question

Я пытался реализовать Edmonds-Karp в C++ для максимального потока, и я написал ее немного по-другому:

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

Интересно, когда я запускал свой код, он дал мне правильные результаты. Поэтому я пошел в Wikipedia's example, где он конкретно показал, как используется задний край. Когда я передал этот график моему коду, Я снова получил правильный ответ. Я также проверил итоговую матрицу потока , и он был идентичен Википедии.

Может кто-нибудь объяснить, почему мы должны добавлять и обновлять задние края и, может быть, привести пример, где они критически важны?

Here «s код, который я написал (обновлен, чтобы включить задний края):

Answer 1

Рассмотрим следующую сеть потока

Пусть первый поток s → у → v → т. (Если вы возражаете, что что BFS Эдмондс-Карп никогда бы не выбрать этот вариант, затем увеличить график с еще несколько вершин между сек и против и между у и т).

без реверсирования потока → у v, что невозможно получить оптимальный поток 20.

Answer 2

попробовать следующий случай:

int main() { 
    Digraph<int> g(8); 
    g.addEdge(0,1,1); 
    g.addEdge(1,2,1); 
    g.addEdge(2,4,1); 
    g.addEdge(0,3,1); 
    g.addEdge(3,4,1); 
    g.addEdge(4,7,1); 
    g.addEdge(3,5,1); 
    g.addEdge(5,6,1); 
    g.addEdge(6,7,1); 

    cout<<g.maxFlowEdmondsKarp(0,7); 

    return 0; 
} 

ваша программа выбирает самый короткий путь 0-3-4-7 первой и не имеет возможности найти 0-1-2-4-7 и 0-3-5-6-7. Вы получаете 1, а 2 - правильный ответ.

ли вы вставили обратно-край, чем можно было бы найти следующие пути:

1. 0-3-4-7
2. 0-1-2-4-3(back-edge!)-5-6-7, получая максимальный поток 2.