Хороший компактный пример одного из самых полезных алгоритмов на графах.
Задача MCMF: провести через сеть максимально возможный поток и одновременно сделать его стоимость минимальной.
В этой реализации:
- residual graph хранит оставшиеся возможности для потока
- SPFA каждый раз ищет самый дешёвый увеличивающий путь
- после поиска определяется bottleneck - сколько потока реально можно протолкнуть по найденному пути
- поток отправляется по пути
- процесс повторяется, пока путь из источника в сток больше найти нельзя
Особенно красивый трюк - обратные рёбра.
Прямое и обратное ребро добавляются подряд, поэтому получить индекс пары можно через:
id ^ 1
Если id чётный, id ^ 1 даст следующее нечётное ребро. Если нечётный - вернёт предыдущее чётное.
MCMF пригодится там, где мало просто найти максимальный поток и у каждого решения есть цена:
• назначение сотрудников на задачи
• логистика
• маршрутизация
• matching с разной стоимостью
• распределение ресурсов
• расписания
Компактный пример того, как residual network, shortest path и greedy augmentation собираются в один мощный алгоритм.