42
правки
Изменения
Исправления 2
== Мотивация ==
Идея аналогична идее, использующейся в [[Алгоритм Джонсона|алгоритме Джонсона]].
При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]] для поиска кратчайшего пути. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]]. Для этого нам надо перевзвесить рёбра графа.
<tex>\,C_{P_{ij}} = C_{ij} + P_i - P_j </tex>
}}
Заметим , что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.
== Использование потенциалов Джонсона ==
Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока до них, или <tex>+\infty</tex> , если она недостижима. Так как <tex>\,C_{ij} + P_i</tex> - это длина какого-то пути до вершины <tex>\,j</tex>, а <tex>\,P_j</tex> - длина минимального пути, то <tex>C_{P_{ij}} \geqslant 0</tex>, что от нас и требовалось.
Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма.
==Реализация==
Модифицируем псевдокод из статьи про [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]:
'''for''' <tex>e \in E</tex> {
<tex>f[e] \leftarrow 0</tex>
}
Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: <tex>p[e] </tex> - расстояние <tex>s \leadsto e</tex>,
если за длину ребра принимается его стоимость.
'''for''' <tex>v \in V</tex> {
<tex>c[v] \leftarrow c[v] + p[v.from] - p[v.to]</tex>
}
'''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
<tex>P \leftarrow</tex> кратчайший в смысле стоимости путь <tex>s \leadsto t</tex>
дополнить поток <tex>f</tex> вдоль <tex>P</tex>
}
==Асимптотика==
Пусть все пропускные способности целочислены.
Обозначим время работы поиска кратчайшего пути <tex>F(V, E)</tex>.
[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Поиске Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] работает за <tex>O(F(V, E) \cdot |f|)</tex>.Если использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то <tex>F(V, E)= V log V + E</tex>. В результате получим время работы <tex>O((V log V + E) \cdot |f|)</tex>. Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]].
== См. также Литература ==* [[Алгоритм Дейкстры]]* [[Алгоритм Форда''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. 2-Беллмана]]* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]* [[Алгоритм Джонсона]]е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
[[Категория: Задача о потоке минимальной стоимости]]
