Алгоритм Эдмондса

Построить график двудольный (элементы слева соединены дугами только с элементами справа, элементы справа не имеют исходящей связи) такой, что элементы слева — это машины, а элементы справа — задачи, подлежащие выполнению . Луки имеют мощность 1 и стоимость согласно таблице назначения. Если поток проходит через ребро (i,j), это означает, что машина i выполняет задачу j.

Чтобы завершить двудольный граф, чтобы сделать его потоковой задачей, каждый левый элемент связан как конечная вершина с фиктивным источником. Каждый линейный элемент привязан как исходная вершина к фиктивной скважине. Все эти дуги имеют пропускную способность 1 и стоимость 0. Для решения задачи о назначениях применим алгоритм из максимальный расход с минимальными затратами на построенный двудольный граф.