Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 02.11.2012, 17:44   #1
SergeyZuzic
Новичок
Джуниор
 
Регистрация: 30.04.2012
Сообщений: 1
Вопрос Алгоритм построения максимального потока

Нужно название данного алгоритма:
Цитата:
Шаг 1. Полагаем i = 0. Пусть 0 - любой допустимый поток в транспортной сети D. (например, полный; можно начинать с нулевого потока: 0 (x), x  X).
Шаг 2. По сети D и потоку i строим орграф приращений I(D, i).
Шаг 3. Находим простую цепь i, являющуюся минимальным путем из v1 в vn в нагруженном орграфе I(D, i) (например, используя алгоритм Форда - Беллмана). Если длина этой цепи равна , то поток i максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи i на максимально допустимую величину ai > 0, где ai  Z (прибавляя ее для каждой дуги x  X, через которую проходит цепь i, к уже имеющейся величине потока по дуге x, если направления x и i совпадают, и, вычитая, если направления x и i противоположны).
SergeyZuzic вне форума Ответить с цитированием
Старый 02.11.2012, 18:07   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Одна из вариаций на тему алгоритма Форда-Фалкерсона, по всей видимости.
Abstraction вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение максимального потока транспортной сети (где ошибка) d3mon4eg Помощь студентам 4 13.06.2015 15:05
Нахождение максимального потока в сетях Delphi ftp123 Помощь студентам 2 02.06.2010 07:26
Алгоритм нахождения, максимального потока в Графе densi2009 Общие вопросы Delphi 0 27.05.2010 23:12
Реализация алгоритма нахождения максимального потока в сети Myasnik Помощь студентам 3 06.01.2008 06:42