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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 30: Строка 30:
  
 
==Алгоритм==
 
==Алгоритм==
На основании теоремы построим алгоритм. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.
+
На основании теоремы построим алгоритм.. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.
  
 
===Описание===
 
===Описание===
Строка 44: Строка 44:
 
===Реализация===
 
===Реализация===
  
Пусть задана структура <tex>Edge</tex>:
+
  '''for''' <tex>e \in E</tex> {
  '''struct''' edge:
+
      <tex>f[e] \leftarrow 0</tex>
    '''int''' from       
+
}
    '''int''' to             
+
'''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
    '''double''' c      <font color=green>// пропускная способность ребра</font>
+
      <tex>P \leftarrow</tex> кратчайший в смысле стоимости путь <tex>s \leadsto t</tex>
    '''double''' flow    <font color=green>// поток через ребро</font>
+
      дополнить поток <tex>f</tex> вдоль <tex>P</tex>
    '''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: Строка 63:
 
==Источники информации==
 
==Источники информации==
 
*[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)
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория: Задача о потоке минимальной стоимости]]
 
[[Категория: Задача о потоке минимальной стоимости]]

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

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

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

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