Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости — различия между версиями
(→Реализация) |
м (rollbackEdits.php mass rollback) |
||
(не показано 6 промежуточных версий 2 участников) | |||
Строка 44: | Строка 44: | ||
===Реализация=== | ===Реализация=== | ||
− | Пусть | + | Пусть задана структура <tex>Edge</tex>: |
'''struct''' edge: | '''struct''' edge: | ||
'''int''' from | '''int''' from | ||
'''int''' to | '''int''' to | ||
− | '''double''' c // пропускная способность ребра | + | '''double''' c <font color=green>// пропускная способность ребра</font> |
− | '''double''' flow // поток через ребро | + | '''double''' flow <font color=green>// поток через ребро</font> |
− | '''double''' price // стоимость перемещения единицы потока через ребро | + | '''double''' price <font color=green>// стоимость перемещения единицы потока через ребро</font> |
− | '''Edge[]''' findMinCostMaxFlow(<tex>G: (V, | + | Будем использовать структуру для хранения ребер графа G. |
+ | |||
+ | '''Edge[]''' findMinCostMaxFlow(<tex>G: (V, E)</tex>, '''int''' s, '''int''' t): | ||
'''for''' edge '''in''' <tex>E</tex>: | '''for''' edge '''in''' <tex>E</tex>: | ||
edge.flow = 0 | edge.flow = 0 | ||
Строка 58: | Строка 60: | ||
P = путь <tex>s \leadsto t</tex> с наименьшей стоимостью. | P = путь <tex>s \leadsto t</tex> с наименьшей стоимостью. | ||
maxFlow = <tex>\displaystyle \min_{edge \in P} edge.c - edge.flow</tex> | maxFlow = <tex>\displaystyle \min_{edge \in P} edge.c - edge.flow</tex> | ||
− | '''for''' edge '''in''' | + | '''for''' edge '''in''' P: |
edge.flow += maxFlow | edge.flow += maxFlow | ||
− | '''return''' | + | '''return''' <tex>E</tex> |
===Асимптотика=== | ===Асимптотика=== |
Текущая версия на 19:15, 4 сентября 2022
Теорема Форда-Фалкерсона
Задача о потоке минимальной стоимости состоит в нахождении среди всех потоков данной величины наименее затратного.
Лемма (о представлении потоков): |
Пусть и — потоки в сети . Тогда можно представить как сумму , где — поток в остаточной сети . |
Доказательство: |
Рассмотрим произвольное ребро Антисимметричность и закон сохранения потока проверяются аналогично из . . Таким образом, поток через каждое ребро не превосходит пропускной способности остаточной сети. лемме о сложении потоков. |
Теорема: |
Пусть: — сеть с истоком и стоком , — поток минимальной стоимости в сети среди потоков величины , — путь минимальной стоимости в остаточной сети.
Тогда: поток — поток минимальной стоимости среди потоков величины , где — поток величины , проходящий по пути . |
Доказательство: |
Пусть лемме о сложении потоков его величина будет равна . — поток минимальной стоимости величины в . Представим , где — поток в остаточной сети . Тогда разность будет потоком в сети и поПо теореме о декомпозиции можно представить как сумму элементарных потоков вдоль путей и циклов . В этом представлении нет отрицательных циклов, иначе прибавление его к даст поток меньшей стоимости. Если есть положительный цикл, то вычтем его из и получим поток меньшей стоимости. Таким образом, для всех циклов. Тогда Отсюда . и поток — минимальный. |
Алгоритм
На основании теоремы построим алгоритм. На каждой итерации алгоритма будем находить путь минимальной стоимости из
в в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.Описание
- Начало.
- Шаг 1. Для каждого ребра зададим поток равный .
- Шаг 2. Построим остаточную сеть .
- Шаг 3. Если существует путь в остаточной сети — перейдем к шагу 4, иначе к шагу 6.
- Шаг 4. Найдем путь c минимальной стоимостью: путь .
- Шаг 5. Дополним поток вдоль пути .
- Шаг 6. Поток минимальной стоимости найден, т.к в остаточной сети не осталось ни одного пути.
- Конец.
Реализация
Пусть задана структура
:struct edge: int from int to double c // пропускная способность ребра double flow // поток через ребро double price // стоимость перемещения единицы потока через ребро
Будем использовать структуру для хранения ребер графа G.
Edge[] findMinCostMaxFlow(, int s, int t): for edge in : edge.flow = 0 while путь в остаточной сети : P = путь с наименьшей стоимостью. maxFlow = for edge in P: edge.flow += maxFlow return
Асимптотика
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его
. В сетях с целочисленной пропускной способностью итераций будет не более .Итого получаем время работы
.См. также
Источники информации
- Wikipedia — Теорема Форда-Фалкерсона
- Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)