Обновить максимальный поток после добавления ребра

Question

Предположим, что у нас есть поток в сети и, используя алгоритм Эдмонда-Карпа, у нас уже есть максимальный поток в сети. Теперь, если мы добавим произвольное ребро (с определенной пропускной способностью) в сеть, каков наилучший способ обновления максимального потока? Я думал об обновлении остаточной сети относительно нового фронта и снова искал пути расширения, пока мы не найдем новый максимальный поток, но я не уверен, работает ли он или это лучший способ!

Answer 1

После выполнения maxflow вы узнаете, сколько контента у каждого края.

Таким образом, когда стоимость ребра изменилась, вы можете сделать следующее:

1. Предположим, что содержимое этого края w,
2. Теперь сделай forward dfs и backward dfs с этого края и отменить всего w содержание от края это связано.

Здесь каждое ребро представлено x/y, где y означает пропускную способность и x означает содержание, которое это потекло.

Теперь вы хотите изменить стоимость края 4->3 от 2 в 3,

Все, что вам нужно сделать, это сделать forward and backward dfs от 4->3 край и расстегнутый 2 вес от этого края как 4->3 потекла w=2 содержание.

Вот процесс будет выглядеть так:

Теперь вы почти закончили:)

3. Изменить стоимость края 4->3 от 2 в 3 и снова попробуйте найти путь расширения:)

Дайте мне знать, если вам трудно понять или я ошибаюсь.

Редактировать:

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

2. Но если емкость уменьшится, вам придется сбросить вес и попытаться найти путь увеличения.

3. Если добавлено новое ребро, вы можете просто добавить ребро и попытаться найти путь увеличения, если он доступен. вот и все.

Answer 2

На самом деле, добавление нового ребра не очень сложно - у вас есть потоки / возможности ребер перед добавлением ребра, а затем вы добавляете ребро и его инверсию. Затем запустите алгоритм, который вы используете, чтобы найти путь расширения, пока не найдете ненулевой поток и все. Большая часть максимального потока уже будет найдена, поэтому это (теоретически) не должно быть слишком медленным. Я не знаю, какой алгоритм максимального потока вы используете, поэтому я не могу быть более конкретным, но возможно, что после добавления нового ребра вы нарушите свойство алгоритма и, таким образом, вы найдете максимальный поток неоптимальным способом. Тем не менее, вы уже обработали большую часть графика, так что это не должно быть слишком большой проблемой.

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