|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
11.05.2015, 22:11 | #1 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Оптимизация поиска пути между двумя вершинами взвешенного ориентированного графа с помощью bfs
День добрый
Давно я начала над этим думать. Сейчас решил поделиться мыслями.. Начну издалека : Самый красивый поиск пути на невзвешенном графе - bfs. Сложность его примерно V*V (или Е, если задаем списком) Основный принцип, заложенный в bfs - первый путь всегда оптимальный. Давайте теперь попробуем применить его на взвешенном графе (для начала возьмем неотрицательные ребра). Для этого нам нужна некая структура, которая позволит за O(logN) (как максимум) вставлять, удалять элемент в упорядоченный ряд. Для этого возьмем кучу (aka очередь с приоритетом). Будешь сортировать по убыванию текущего веса. Алгоритм получается примерно такой : Код:
Код:
Сложность. Очень просто. (V*V*logV) (или E*logV) Можно написать Дейкстру. Сложность (V*V) На логарифм я проигрываю.. А теперь давайте возьмем любые ребра (и скажем, что у нас нет цикла отрицательного веса) Прекрасно. Теперь запускаем тот же самый алгоритм и любуемся, как сложность с (V*V*logV) увеличивается до (V*V*V*logV) (или V*E*logV) Задача с любыми ребрами решается Форд-Беллманом. И его сложность (V*V*V) или (V*E). Я снова проигрываю логарифм.. Теперь ради чем темка создавалась : Не могли бы Вы подсказать, что я не учел? Можно у меня есть какой-то косяк, который я в упор не вижу? И не могли бы Вы подсказать, можно ли как-то улучшить эффективность? Спасибо! Удачи! |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
кратчайший путь между двумя заданными вершинами графа | mimino46 | Общие вопросы C/C++ | 0 | 29.11.2013 22:33 |
Поиск всех путей между двумя вершинами ориент. графа(Язык С) | dasterse | Помощь студентам | 0 | 13.05.2012 17:18 |
длина пути между двумя вершинами в графе | rubakKa | Общие вопросы C/C++ | 5 | 19.12.2010 17:54 |