Лучший алгоритм для минимальной стоимости максимального потока?

Question

Может ли кто-нибудь сказать мне, какой алгоритм является лучшим для максимального потока с минимальными затратами (и который легко реализовать) и откуда будет полезно читать? Я поискал в Интернете и нашел названия многих алгоритмов, но не смог решить, какой из них изучить.

Answer 1

Исходя из моего опыта сравнительного анализа MCF в отраслевых условиях, существует три конкурентоспособных общедоступных реализации: * Масштабирование стоимости библиотеки Lemon от Coin-OR реализация .

Сетевой симплекс Coin-OR реализация .

Я бы попробовал те, что в этом закажите, если вы ограничены во времени. Другие достойные упоминания:

1. масштабирование затрат Google-OR реализация . Я не тестировал это, но ожидаю, что он будет конкурентоспособным с вышеперечисленными.
2. MCFClass имеет несколько реализаций , перечисленных под различными ограниченными лицензиями для коммерческого использования. RelaxIV очень конкурентоспособен, но ограничен.

С точки зрения изучения литературы и обзора конкурентных алгоритмов, работы Кирарли и Ковач являются отличной отправной точкой.