Нахождение максимального пропускного потока

Path: Математика » Графы и маршруты » Максимальный поток

Нахождение максимального пропускного потока

Заметим, во-первых, что это задача линейного программирования, так что ее можно решать симплекс-методом. Более того, теорема о максимальном потоке и минимальном разрезе - в точности теорема двойственности для задачи линейного программирования.

Hо для этой конкретной задачи есть более просто описываемый алгоритм - алгоритм Форда-Фалкерсона (в сущности, это и есть симплекс-метод, примененный в конкретной ситуации).

Алгоритм, грубо говоря, жадный. Hайдем сначала хоть какой-то поток ненулевого веса (нужно найти путь из истока в сток, желательно, с максимальным весом (чтобы алгоритм быстрее работал); можно для этого применить соответствующим образом модифицированный алгоритм Дейкстры).

После этого на кажом шаге алгоритма смотрим, можем ли мы модифицировать наш поток так, чтобы его вес стал больше. Если так модифицировать нельзя, то мы нашли максимальный поток.

Модификация заключается в следующем. Попытаемся "прибавить" к нашему потоку новый. Для этого рассмотим новый граф с теми же вершинами, но новыми пропускными способностями ребер: если пропускная способность ребра от вершины A к вершине B равна c, а в нашем потоке по этому ребру пущено x, то в новом графе есть ребро от A к B с пропускной способностью c-x и ребро от B к A с пропускной способностью x (грубо говоря, мы можем увеличить поток по этому ребру максимум на c-x или уменьшить максимум на x).

После этого в новом графе ищем какой-нибудь поток из истока в сток ненулевого веса (снова можно применить что-нибудь вроде Дейкстры). Если такого нет - ура, тот поток, который у нас был - максимальный. Если есть - складываем эти два потока, получаем новый, с большим весом. Повторяем процесс.

К сожалению, этот алгоритм (как и симплекс-метод) не гарантирует, что время работы полиномиально (если нет ограничений на пропускные способности). В _подавляющем_ _большинстве_ случаев это так, но можно придумать "плохие" примеры, для которых время работы будет экспоненциальным (но в практических задачах они вряд ли встретятся).

Если известно, что пропускные способности ребер - "небольшие" целые числа, то алгоритм действительно работает за O(N³).

Обсудить на форуме »

Комментарии для веб-мастера

	Автор: Артем
	Время: 23-05-03 09:47

	А может кто-нибудь прислать примкр реализации этого алгоритма? Заранее спасибо.

	Автор: Антон
	Время: 18-06-03 09:31

	Хотелось бы еще увидеть алгоритм проталкивания предпотока.

	Автор: 1
	Время: 11-11-03 10:02

	Извините, но что ЭТО за .... ...что-нибудь вроде Дейкстры... ...не гарантирует, что время работы полиномиально... если использовать не что-нибудь вроде Дейкстры а поиск в ширину то время работы будет полиноминальным а время O(N^3) а O(V*E^2), где V и E - число вершин / рёбер - соответственно ...нужно найти путь из истока в сток, желательно, с максимальным весом (чтобы алгоритм быстрее работал); ... Докажи!!! ..._подавляющем_ _большинстве_... Опять же докажи + (см выше)

	Автор: Денис
	Время: 05-12-03 12:25

	Маленькое замечание по времени работы: Метод Время (АС) Память (ЕС) 1 Форд и Фалкерсон (1956)[] nmU m 2 Эдмондс и Карп (1972)[] m^2n m 3 Диниц (1970)[] mn^2 m 4 Карзанов (1974)[] n^3 n2 5 Черкасский (1976)[] n^2m^(1/2) m 6 Малхотра и др. (1978)[] n^3 m 7 Галил и Наамад (1980)[] nm(log n)^2 m 8 Голдберг и Тарьян (1988)[] nmlog(n^2/m) m 9 Ахьюджа и Орлин (1989)[] nm+n^2logU m 10 Голдберг и Рао (1997)[] min(n^(2/3),m^(1/2))m m

	Автор: Вася
	Время: 12-12-03 08:21

	Народ, а кто-нибудь знает алгоритм отыскания минимального потока в транспортной сети (по сути переделанный алгоритм Форда-Фалкерсона , только в извращенной форме). Нам по курсачу задали. Некоторые идеи есть, но уж что-то нехорошие. Если кто-то зтает или просто может помочь, ответте пожалуйста. Буду очень благодарен. Спасибо за внимание.