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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 30: Строка 30:
  
 
==Алгоритм==
 
==Алгоритм==
На основании теоремы построим алгоритм. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.
+
На основании теоремы построим алгоритм.. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.
  
===Описание===
+
===Реализация===
 
* Начало.
 
* Начало.
 
* '''Шаг 1'''. Для каждого ребра зададим поток равный <tex>0</tex>.
 
* '''Шаг 1'''. Для каждого ребра зададим поток равный <tex>0</tex>.
Строка 41: Строка 41:
 
* '''Шаг 6'''. Поток минимальной стоимости найден, т.к в остаточной сети не осталось ни одного пути.
 
* '''Шаг 6'''. Поток минимальной стоимости найден, т.к в остаточной сети не осталось ни одного пути.
 
* Конец.
 
* Конец.
 
===Реализация===
 
 
Пусть задана структура <tex>Edge</tex>:
 
'''struct''' edge:
 
    '''int''' from       
 
    '''int''' to             
 
    '''double''' c      <font color=green>// пропускная способность ребра</font>
 
    '''double''' flow    <font color=green>// поток через ребро</font>
 
    '''double''' price  <font color=green>// стоимость перемещения единицы потока через ребро</font>
 
 
Будем использовать структуру для хранения ребер графа G.
 
 
'''Edge[]''' findMinCostMaxFlow(<tex>G: (V, E)</tex>, '''int''' s, '''int''' t):
 
    '''for''' edge '''in''' <tex>E</tex>:
 
        edge.flow = 0
 
    '''while''' <tex>\exists</tex> путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>:
 
        P = путь <tex>s \leadsto t</tex> с наименьшей стоимостью.
 
        maxFlow = <tex>\displaystyle  \min_{edge \in P} edge.c - edge.flow</tex>
 
        '''for''' edge '''in''' P:
 
            edge.flow += maxFlow
 
    '''return''' <tex>E</tex>
 
  
 
===Асимптотика===
 
===Асимптотика===
Строка 75: Строка 53:
 
==Источники информации==
 
==Источники информации==
 
*[https://ru.wikipedia.org/wiki/Теорема_Форда_—_Фалкерсона Wikipedia {{---}} Теорема Форда-Фалкерсона]
 
*[https://ru.wikipedia.org/wiki/Теорема_Форда_—_Фалкерсона Wikipedia {{---}} Теорема Форда-Фалкерсона]
 +
 +
== Литература ==
 
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)
 
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория: Задача о потоке минимальной стоимости]]
 
[[Категория: Задача о потоке минимальной стоимости]]

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

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

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

Шаблоны, используемые на этой странице: