Почему в Edmonds-Karp Maximum Flow нужно учитывать задние кромки?

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

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

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

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

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

4

Решение

Рассмотрим следующую сеть потоков
введите описание изображения здесь

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

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

3

Другие решения

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

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.
3

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector