Я пытаюсь найти эффективный общедоступный алгоритм, желательно с реализацией, для решения максимального потока в обобщенной (нечистой) сети с усилением. Все множители, емкости и значения расхода являются целыми числами, отличными от нуля.
Существует ли такой алгоритм или эта задача не решается за полиномиальное время?
Вот несколько ссылок на некоторые алгоритмы и некоторые пояснения:
Это мое решение для максимального потока: извините за имя переменной, я тогда был молод :) http://infoarena.ro/job_detail/431616?action=view-source
Надеюсь, это помогло
Первый (строго) полиномиальный алгоритм был опубликован Вегом в 2013 году, и с тех пор он улучшено Олвером и Вегом до наихудшего времени выполнения в O((m + n log n) m n log(n^2 / м)). Но я не знаю какой-либо общедоступной реализации этого алгоритма.
Связанные документы также содержат ссылки на более ранние (слабо) полиномиальные алгоритмы, а также на приближенные алгоритмы, некоторые из которых могут иметь общедоступные реализации. (В этой старой статье Тардоса и Уэйна упоминается C++ реализация.)
