Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
1

Несколько запусков Дейкстры или всё же Флойд?

22.05.2013, 00:10. Просмотров 655. Ответов 5
Метки нет (Все метки)

Здравствуйте.Хотел бы спросить по поводу решения одной задачи.

Есть граф.Надо найти расстояние от 1 вершины до 2, от 2 до 3,от3 до 4 и т д.

Так вот, какое решение будет быстрее работать - 1 запуск Флойда(n в 3), или серия запусков Дейкстры(m log n n раз)

По асимптотике вроде Дейкстра лучше, но хотелось бы услышать мнения более опытных людей.Или существуют ещё другие, более эффективные решения?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.05.2013, 00:10
Ответы с готовыми решениями:

Запись и извлечение данных в несколько запусков программы
Всем добрый вечер! Предоставляю исходник программы EMPL_IO стр.574 с книги...

Получить из строки всё до пробела или запятой или точки или восклицательного знака
Match m_ = Regex.Match(вопрос, @"Кто такой.(.{5})", RegexOptions.IgnoreCase |...

Участие в Open Source,KDE, проекты, qtbase5-dev и всё всё всё
Адресовано к разработчикам, кто на линуксе участвует в разработке опен-сорс...

Алгоритм Флойд
всем привет) помогите с алгоритмом Флойда пожалуйста(на С). программа поиска...

Заблокирована панель задач или опции программ или всё вместе
Бывает что после включения/перезагрузки ПК щелкаешь мышью по панели задач, и...

5
Dmitriy_M
1433 / 1313 / 131
Регистрация: 20.03.2009
Сообщений: 4,688
Записей в блоге: 11
22.05.2013, 07:40 2
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
(m log n n раз)
откуда такая асимптотика?

Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
По асимптотике вроде Дейкстра лучше
В простейшем случае асимптотика одинаковая, в остальных будет зависеть от реализации, и не стоит забывать про константы внутри O().
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
22.05.2013, 11:50  [ТС] 3
Dmitriy_M, асимптотика m log n взята с емакса(я реализовываю Дейкстру через кучу(priority_queue), а у такой реализации эта асимптотика).А так как я запускаю от каждой вершины Дейкстру, то всё это умножаем на n.Но вот насчёт констант внутри я не знаю.Наверное всё решит только тест))
0
Dmitriy_M
1433 / 1313 / 131
Регистрация: 20.03.2009
Сообщений: 4,688
Записей в блоге: 11
22.05.2013, 18:13 4
Насколько понимаю http://www.cyberforum.ru/cgi-bin/latex.cgi?E\log{V} справедливо только для разреженных графов.
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
22.05.2013, 18:56  [ТС] 5
Dmitriy_M, согласно емаксу - да
0
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
23.05.2013, 16:39 6
если перед вами стоит задача найти матрицу кратчайших путей между всеми парами вершин, то используйте алгоритм Флойда.

как вы собрались Дейкстрой за m*n*log(n) это сделать?

у Дейкстры за логарифм гораздо хуже константы. это оправдано, когда граф разряжен, но когда он плотный вы вместо трехстрочного n^3 получите довольно непростой n^3*(большой коэффициент)...
0
23.05.2013, 16:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2013, 16:39

Не работает флойд-уоршалл
Написал алгоритм, проверяю его на матрице смежности : 0 19 2 1 8 0 0 0 5 0...

Через несколько POST-запросов всё перестаёт работать
Программа отсылает POST запросы серверу. Запросы отсылаются с помощью...

Несколько открытых страниц браузера, сессии и вот это всё
Привет программисты! Во первых спасибо за форум создателям. Хочу услышать...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru