| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск потока минимальной стоимрсти в графе |
| Автор: anna 3.5.2006, 22:08 |
| Столкнулась с проблемой - нигде четко алгоритм не сформулирован, да и исходников нет. =( Алгоритм-то вроде интересный, да и вытекает из алгоритма поиска максимального потока. Может, кто- нить что дельное предложит? |
| Автор: Romikgy 3.5.2006, 23:38 |
| не понятно че это и что нужно? |
| Автор: popolzen 4.5.2006, 10:21 |
| В таких случаях можно поступить так: 1 способ: Изменяешь знаки стоимостей в графе на противоположные и ищешь поток по алгоритму поиска максимального потока. Надеюсь, ты понимаешь, почему это так. 2 способ (если алгоритм не работает с отрицательными числами): Находишь ребро с максимальным весом (max), затем вес каждого ребра вычисляется как max - вес ребра. Далее поиск максимального потока. Если что-то непонятно, спрашивай. |
| Автор: Alagert 4.5.2006, 12:12 |
| На эту тему можно почитать в Кормене. Там довольно детально все описано. |
| Автор: anna 4.5.2006, 18:29 |
| Ооо, за Кормана спасибо.=) Реальная вещь. popolzen, я тебя не совсем поняла... Ну да ладно, в Кормане всеописано=) |