| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Максимальный поток в сети |
| Автор: fandorin 14.4.2008, 01:06 |
| Здравствуйте, задача заключается в следующем: необходимо найти максимальный поток в сети, пропускная способность ребер которой равна 1. Реально ли найти алгоритм, работающий за порядка O(V), где V - число вершин, в такой ситуации? Заранее благодарен за ваши ответы. |
| Автор: maxdiver 14.4.2008, 08:07 |
| Нереально. Поскольку число рёбер в графе есть в худшем случае O(V^2), а любой алгоритм должен хотя бы раз просмотреть каждое ребро, то любой алгоритм будет асимптотически не лучше O(V^2). |
| Автор: fandorin 15.4.2008, 09:35 |
| Это верно конечно, но если вычисления распараллелить, то можно добиться хорошего результата, я вот и пытаюсь найти подходящий алгоритм. Сейчас есть идея попробовать разобраться в алгоритме Голдберга-Рао, оценка для которого при параллельных вычислениях O(V). Может быть у кого есть хорошее описание алгоритма и программная реализация (все равно на каком языке программирования)? |