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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Здесь <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

Здесь [math]f[/math] -- поток, [math]c[/math] -- пропускная способность, а цена-то как обозначается? Мне кажется, в статье под [math]c[/math] в некоторых местах подразумевается стоимость, а в некоторых -- пропускная способность.

  • Шаг 4. При помощи алгоритма Форда-Беллмана найдем отрицательные циклы в остаточной сети (но разве можно найти все циклы сразу?). Если нет — перейдем к шагу 7.
  • Шаг 6. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Перейдем к шагу 5 (но ведь остаточная сеть изменилась и могли появиться новые циклы, которые надо ещё найти).

(асимптотика скорее всего неверная, т.к. не учитывает красные замечания выше)