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

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

Версия 00:56, 24 января 2016

Задача

Задача о потоке минимальной стоимости состоит в нахождении среди всех потоков данной величины наименее затратного.

Идея

В основе алгоритма лежит теорема Форда-Фалкерсона о потоке минимальной стоимости. На каждой итерации алгоритма будем находить путь минимальной стоимости из [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)