Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Идея)
(Идея)
Строка 1: Строка 1:
 
==Идея==
 
==Идея==
 
В основе алгоритма лежит [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теорема Форда-Фалкерсона о потоке минимальной стоимости]]. На каждой итерации алгоритма будем находить путь из  <tex>s</tex> в <tex>t</tex> минимальной стоимости и дополнять поток вдоль этого пути.
 
В основе алгоритма лежит [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теорема Форда-Фалкерсона о потоке минимальной стоимости]]. На каждой итерации алгоритма будем находить путь из  <tex>s</tex> в <tex>t</tex> минимальной стоимости и дополнять поток вдоль этого пути.
У нас появляются ребра отрицательного веса. Выбирать алгоритм для поиска кратчайших путей следует с учетом этого факта.
+
Так как появляются ребра отрицательного веса. Выбирать алгоритм для поиска кратчайших путей следует с учетом этого факта.
  
 
==Реализация==
 
==Реализация==

Версия 07:25, 17 января 2012

Идея

В основе алгоритма лежит теорема Форда-Фалкерсона о потоке минимальной стоимости. На каждой итерации алгоритма будем находить путь из [math]s[/math] в [math]t[/math] минимальной стоимости и дополнять поток вдоль этого пути. Так как появляются ребра отрицательного веса. Выбирать алгоритм для поиска кратчайших путей следует с учетом этого факта.

Реализация

for [math]e \in E[/math] {
     [math]f[e] \leftarrow 0[/math]
}
while (существует путь [math]s \leadsto t[/math] в остаточной сети [math]G_f[/math]) {
      [math]P \leftarrow[/math] кратчайший в смысле стоимости путь [math]s \leadsto t[/math]
      дополнить поток [math]f[/math] вдоль [math]P[/math]
}

Корректность

Непосредственно следует из теоремы Форда-Фалкерсона о потоке минимальной стоимости.

Асимптотика

Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его [math]F(V, E)[/math]. В сетях с целочисленной пропускной способностью итераций будет не более [math]|f|[/math].

Итого получаем время работы [math]O(F(V, E) \cdot |f|)[/math].

Литература

  • Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)