Совершенное паросочетания минимальной стоимости

[DidiSD]

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

[sup]

Если Вас интересует алгоритм Эдмондса, то я его видел в книге
Ловас. Пламмер. Прикладные задачи теории графов.

[helgui]

Задача о назначениях довольно просто сводится к min-cost-max-flow. При решении min-cost-max-flow можно воспользоваться алгоритмом Дейкстры для поиска дополняющего пути.