Алгоритм Форда-Фулкерсона с "взвешенными" ребрами

Question

Есть ли какой-нибудь вариант Ford-Fulkerson, который добавляет дополнительное измерение "веса" к краям?

Под этим я подразумеваю, что некоторые ребра более идеальны, чем другие, и, хотя все возможности есть, он будет определять приоритеты идеальных ребер над меньшими идеальными ребрами.

Answer 1

Есть два общих обобщения, о которых я знаю, чтобы добавить веса.

Минимальный расход

Предположим, у вас есть вес для каждого ребра и вы хотите вычислить поток, который удовлетворяет ограничениям и имеет минимальные затраты. (Стоимость = сумма веса * единиц, проходящих вдоль соответствующего края)

Эта проблема называется минимальным потоком затрат.

Реализация может быть найдена в networkx и называется min-cost-flow.

Вот хороший урок по topcoder'у по первично-двойственному подходу.

Мой любимый алгоритм для этого был на самом деле изобретен самим Фулкерсоном в 1961 году и называется алгоритмом " вне работы".

Максимальный расход минимальная стоимость

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

Это отличается от первой интерпретации тем, что минимальный расход может не дать максимально возможный поток. Например, предположим, что у нас есть одно ребро начало-> конец с ограничением, что поток находится в диапазоне от 0 до 1, и весом 1.

Поток минимальной стоимости будет потоком 0, в то время как максимальный поток минимальной стоимости будет потоком 1.

Реализация этого может быть найдена в networkx под названием max_flow_min_cost.