|
DidiSD |
|
|
|
Добрый день.
Никто не поможет ссылкой на алгоритм для нахождения совершенного паросочетания минимальной стоимости (по сути она же задача о назначениях) используя в основе поиск пути минимальной стоимости (дейкстры). День потратил, много где описано, что это есть, но алгоритм не нашел. По сути нужно только описание идеи.
|
|
|
|
 |
|
sup |
|
|
|
Если Вас интересует алгоритм Эдмондса, то я его видел в книге
Ловас. Пламмер. Прикладные задачи теории графов.
|
|
|
|
|
|
helgui |
|
|
|
Задача о назначениях довольно просто сводится к min-cost-max-flow. При решении min-cost-max-flow можно воспользоваться алгоритмом Дейкстры для поиска дополняющего пути.
|
|
|
|
|
