Форум программистов, компьютерный форум, киберфорум
Наши страницы

Поиск циклов в графе. Поиск центра взвешенного графа - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Списки:нужны или нет? http://www.cyberforum.ru/cpp-beginners/thread944104.html
Стоит ли изучать связные списки,они используются в дальнейшем? Может я туповат, но алгоритм их построения понять не могу. Уж больно все запутанно описывается в книжке. Пытался сам разбираться ,вот...
C++ Путь символа Здорова господа! Есть интересная задачка: "Проследите путь символа в вашей системе от клавиатуры до экрана на примере следующего кода:" char c; cin >>c; cout <<c<<endl; И как же его... http://www.cyberforum.ru/cpp-beginners/thread944099.html
C++ Ошибка: "case label not within a switch statement"
Здравствуйте, работая с оператором switch произошла ошибка case label '1' not within a switch statement case label '1' not within a switch statement case label '1' not within a switch statement...
C++ Время для функции генерирующей случайные величины
я написал функцию которая генерирует случайные величины в промежутке valarray<double> cRand::base_rnd(size_t N){ valarray<double> v; v.resize(N); int x,y; int x0 = time(0); x =...
C++ Конструктор класса http://www.cyberforum.ru/cpp-beginners/thread944077.html
class A{}; class B : public A { B(); }; B::B() : A() /// ДЛЯ ЧЕГО ТУТ :A() И ЧТО ЭТО ОЗНАЧАЕТ??? { }
C++ Конструктор класса Я не могу понять вот эту запись class A{}; class B : public A { подробнее

Показать сообщение отдельно
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
27.08.2013, 18:14
Цитата Сообщение от iRomul Посмотреть сообщение
есть метод Флойда-Уоршелла, который за O(n^3) даёт пути ...
а еще есть алгоритм Дейкстры (для случаев когда нет отрицательных весов ребер), который дает тот же результат за V*E*logV (V - кол-во вершин, E - кол-во ребер), а также алгоритм Беллмана-Форда (для случая когда есть отрицательные ребра, но нет отрицательных циклов) с примерно такой же оценкой времени. И какой из них выбирать зависит от насыщенности графа. Так что выбор конкретного алгоритма поиска путей пусть будет на совести ТСа.
Цитата Сообщение от iRomul Посмотреть сообщение
... из всех вершин во все остальные.
вот именно ИЗ (я же специально капсом написал), а нам надо В. а это уже другая история.
Цитата Сообщение от iRomul Посмотреть сообщение
Рекомендую книгу Кормена по алгоритмам - там всё просто и понятно, с псевдокодами и иллюстрациями.
а тут поддерживаю

Добавлено через 2 минуты
Цитата Сообщение от iRomul Посмотреть сообщение
А циклы в графе надо смотреть либо Эйлера, либо Гамильтона.
зачем? и простых будет достаточно, даже больше скажу: достаточно и необходимо
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.