Использование потенциалов Джонсона при поиске потока минимальной стоимости — различия между версиями
(Новая страница: «== Потенциал Джонсона == {{Определение |definition=Пусть дана транспортная сеть <math>\,G(V,E)</math>. Введ…») |
|||
| Строка 6: | Строка 6: | ||
Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины. | Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины. | ||
| − | == Использование | + | == Использование потенциалов Джонсона == |
Если <math>\forall i, j \,C_{P_{ij}} \geqslant 0</math> то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма. | Если <math>\forall i, j \,C_{P_{ij}} \geqslant 0</math> то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма. | ||
Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или <math>+\infty</math> если она недостижима. Так как <math>\,C_{ij} + P_i</math> это длина какого-то пути до вершины <math>\,j</math>, а <math>\,P_j</math> - длина минимального пути, то <math>C_{P_{ij}} \geqslant 0</math>, что от нас и требовалось. | Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или <math>+\infty</math> если она недостижима. Так как <math>\,C_{ij} + P_i</math> это длина какого-то пути до вершины <math>\,j</math>, а <math>\,P_j</math> - длина минимального пути, то <math>C_{P_{ij}} \geqslant 0</math>, что от нас и требовалось. | ||
Версия 01:22, 16 января 2011
Потенциал Джонсона
| Определение: |
| Пусть дана транспортная сеть . Введем в каждой вершине потенциал . Тогда остаточная стоимость ребра определяется как |
Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.
Использование потенциалов Джонсона
Если то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма.
Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или если она недостижима. Так как это длина какого-то пути до вершины , а - длина минимального пути, то , что от нас и требовалось.
