Почему в Edmonds-Karp Maximum Flow нужно учитывать задние кромки?
Я пытался реализовать Эдмондс-Karp в C ++ для максимального потока, и я написал это немного по-другому:
- Вместо того, чтобы проходить все ребра в остаточном графе, я прошел только ребра, присутствующие в исходном графе, используя список смежности.
- Я не обновлял какие-либо фоны при обновлении остаточного графа с минимальным потоком.
Интересно, что когда я запустил свой код, он дал мне правильные результаты. Итак, я пошел в Пример Википедии, где это конкретно показать, как используется задний край. Когда я подал этот график в мой код, Я снова получил правильный ответ.
Я также проверил результирующая матрица потока, и это было идентично Википедии.
Может кто-нибудь объяснить, почему мы должны добавить и обновить back-ребра, а может привести пример где они критичны?
Воткод, который я написал (обновлен, чтобы включить задние края):
Решение
Рассмотрим следующую сеть потоков
Предположим, что первый поток s → u → v → t. (Если вы возражаете против того, что BFS Эдмондса-Карпа никогда не выберет это, то добавьте в граф еще несколько вершин между s а также v и между U а также T).
Без реверсивного потока u → v, невозможно получить оптимальный поток 20.
Другие решения
Попробуйте следующий случай:
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 будет правильным ответом.
Если бы вы вставили задний край, то вы найдете следующие пути:
0-3-4-70-1-2-4-3(back-edge!)-5-6-7, получая максимальный поток 2.