Алгоритм отмены

Алгоритм отмены цикла минимального среднего веса

Приведенный алгоритм принадлежит к классу сильно полиномиальных алгоритмов.

Определение:

Сильно полиномиальными в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от [math]V[/math] — числа вершин и [math]E[/math] — числа ребер графа.

Описание алгоритма

Рассмотрим некоторый цикл [math]C[/math]. Обозначим его стоимость за [math]p(C)[/math], а его длину (число ребер, входящих в цикл) за [math]\texttt{len}(C)[/math].

Определение:

Средним весом цикла называется отношение его стоимости к его длине [math]\mu (C)=\frac{p(C)}{\texttt{len}(C)}[/math]

Сам алгоритм

Рассмотрим некоторый поток [math]f[/math]. Находим цикл [math]C[/math], обладающий наименьшим средним весом. Если [math]\mu (C) \geq 0[/math], то [math]f[/math] — поток минимальной стоимости и алгоритм завершается. Иначе, отменим цикл [math]C[/math]: [math]f := f + c_{f}(C)\cdot f_{C}, где \lt tex\gt c_{f}(C) {{---}} остаточная пропускная способность цикла \lt tex\gt C[/math]. Вернемся к началу алгоритма.

Время работы алгоритма

[math]O(VE\cdot VE^{2}\log{V})[/math]

Алгоритм поиска цикла минимального среднего веса