Редактирование: Поток минимальной стоимости

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 23: Строка 23:
 
====Алгоритм====
 
====Алгоритм====
 
* '''Начало.'''
 
* '''Начало.'''
* '''Шаг 1'''. Определим для каждого прямого ребра <tex>(u,v)</tex> обратное ребро <tex>(v,u)</tex>. Определим его характеристики: <tex>c(v,u)=0</tex>, <tex>f(v,u)=-f(u,v)</tex>, <tex>a(v,u)=-a(u,v)</tex>.
+
* '''Шаг 1'''. Требуется найти максимальный поток минимальной стоимости.
 
* '''Шаг 2'''. Для каждого ребра зададим поток равный <tex>0</tex>.
 
* '''Шаг 2'''. Для каждого ребра зададим поток равный <tex>0</tex>.
* '''Шаг 3'''. Найдем произвольный максимальный поток(любым алгоритмом нахождения максимального потока), построим для него остаточную сеть, где каждому ребру будет соответствовать величина <tex>a(u,v) \cdot (c(u,v) - f(u,v))</tex>.
+
* '''Шаг 3'''. Построим остаточную сеть <tex>G_f</tex>.
* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательный цикл в построенной сети (отрицательный цикл ищется по стоимости ребра, т.е. ребра имеют вес <tex>a(u,v)</tex>). Если отрицательный цикл не нашелся {{---}} перейдем к '''шагу 6'''.
+
* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательные циклы в остаточной сети. Если нет {{---}} перейдем к '''шагу 7'''.
* '''Шаг 5'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Величина потока равна минимальной остаточной пропускной способности в цикле. Перейдем к '''шагу 4'''.
+
* '''Шаг 5'''. Выберем один из отрицательных циклов.
* '''Шаг 6'''. Отрицательных циклов в остаточной сети нет, значит, максимальный поток минимальной стоимости найден.
+
* '''Шаг 6'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Перейдем к '''шагу 5'''.
 +
* '''Шаг 7'''. Отрицательных циклов в остаточной сети нет, значит, максимальный поток минимальной стоимости найден.
 
* '''Конец.'''
 
* '''Конец.'''
  
 
====Асимптотика====
 
====Асимптотика====
Алгоритм Форда-Беллмана работает за <tex>O(VE)</tex>, улучшение цикла за <tex>O(E)</tex>. Если обозначить максимальную стоимость потока как <tex>C</tex>, а максимальную пропускную способность как <tex>U</tex>, то алгоритм совершит <tex>O(ECU)</tex> итераций поиска цикла, если каждое улучшение цикла будет улучшать его на 1. В итоге имеем <tex>O(V E^2 C U + maxFlow)</tex>, где <tex>maxFlow</tex> - асимптотика поиска максимального потока.
+
Алгоритм Форда-Беллмана работает за <tex>O(VE)</tex>. Нахождение максимального потока и улучшение цикла работает за <tex>O(E)</tex>. В итоге имеем <tex>O(V E^2)</tex>.
  
 
===Метод дополнения потока вдоль путей минимальной стоимости===
 
===Метод дополнения потока вдоль путей минимальной стоимости===
{{main|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости}}
+
{{main|Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости}}
  
 
===Использование потенциалов Джонсона===
 
===Использование потенциалов Джонсона===
{{main|Использование потенциалов Джонсона при поиске потока минимальной стоимости}}
+
{{main|Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости}}
  
 
== См. также ==
 
== См. также ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)