Обсуждение:Поток минимальной стоимости — различия между версиями
(Новая страница: «Здесь <math>f</math> -- поток, <math>c</math> -- пропускная способность, а цена-то как обозначается? Мне ...») |
|||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
Здесь <math>f</math> -- поток, <math>c</math> -- пропускная способность, а цена-то как обозначается? Мне кажется, в статье под <math>c</math> в некоторых местах подразумевается стоимость, а в некоторых -- пропускная способность. | Здесь <math>f</math> -- поток, <math>c</math> -- пропускная способность, а цена-то как обозначается? Мне кажется, в статье под <math>c</math> в некоторых местах подразумевается стоимость, а в некоторых -- пропускная способность. | ||
| + | |||
| + | * '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательные циклы в остаточной сети <span style="color: red">(но разве можно найти все циклы сразу?)</span>. Если нет {{---}} перейдем к '''шагу 7'''. | ||
| + | |||
| + | * '''Шаг 6'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Перейдем к '''шагу 5''' <span style="color: red">(но ведь остаточная сеть изменилась и могли появиться новые циклы, которые надо ещё найти)</span>. | ||
| + | |||
| + | <span style="color: red">(асимптотика скорее всего неверная, т.к. не учитывает красные замечания выше)</span> | ||
Текущая версия на 16:17, 12 февраля 2018
Здесь -- поток, -- пропускная способность, а цена-то как обозначается? Мне кажется, в статье под в некоторых местах подразумевается стоимость, а в некоторых -- пропускная способность.
- Шаг 4. При помощи алгоритма Форда-Беллмана найдем отрицательные циклы в остаточной сети (но разве можно найти все циклы сразу?). Если нет — перейдем к шагу 7.
- Шаг 6. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Перейдем к шагу 5 (но ведь остаточная сеть изменилась и могли появиться новые циклы, которые надо ещё найти).
(асимптотика скорее всего неверная, т.к. не учитывает красные замечания выше)
