|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
24.11.2010, 16:31 | #1 |
Регистрация: 16.11.2010
Сообщений: 7
|
Алгоритм Дейкстры. Быстродействие
День добрый. Написал алгоритм Дейкстры и обнаружил что он весьма медленно работает на больших графах(число вершин больше 1000), вот код:
Код:
Не подскажите как можно было бы улучшить алгоритм или следует применять алгоритм Йена? |
24.11.2010, 16:57 | #2 |
C++ hater
СтарожилДжуниор
Регистрация: 19.07.2009
Сообщений: 3,333
|
слишком много циклов и избыточная глубина. в классическом алгоритме дейкстры нет тройного вложенного цикла
I invented the term Object-Oriented, and I can tell you I did not have C++ in mind. (c)Alan Kay
My other car is cdr. Q: Whats the object-oriented way to become wealthy? A: Inheritance |
25.11.2010, 01:46 | #3 |
Регистрация: 16.11.2010
Сообщений: 7
|
Ну классический алгоритм для двух вершин, разве не так? Для N нужно делать либо N переборок, либо искать наименьшего предка, если таковой уже найден, но могу быть и не прав, но что-то давно уже вожусь с этим. В начале написал флойда-уоршела, и тот после оптимизации стад давать даже лучший результат чем этот в своем нынешнем виде. Не могу понять почему, тк даже в случае тройных циклов Ф-У должен явно проигрывать, но по тестам получается что нет. Видимо придется провозиться еще не один день.
PS: не подскажите где можно прочитать подробно про алгоритм Йена? Есть мнение что его лучше брать при большом числе вершин. |
10.12.2010, 14:30 | #4 |
Форумчанин
Регистрация: 20.06.2008
Сообщений: 125
|
1) Вы для поиска вершины с минимальным расстоянием, используете обычный линейный поиск. Получим O(n^3) операций.
Нужно использовать приоритетную очередь, и список смежностей вместо матрицы. O(n^2 * log(n)). 2) Алгоритм Дейкстры рассчитан на поиск путей от одной вершины до всех. А запускать его n раз - слишком расточительно. Тут действительно нужно что-нибудь другое. Например Джонсона. Он хоть и имеет ту же асимптотику, но должен работать быстрее. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм Дейкстры (С++) | DemonScorpion | Помощь студентам | 4 | 18.11.2015 18:41 |
Алгоритм Дейкстры | Opiym | Общие вопросы .NET | 1 | 29.05.2010 17:04 |
Алгоритм Дейкстры | tarnis | Общие вопросы Delphi | 4 | 11.05.2010 14:00 |
Алгоритм Дейкстры | andis | Помощь студентам | 0 | 24.01.2010 17:42 |
Алгоритм Дейкстры | Dimon88 | Помощь студентам | 2 | 03.11.2007 17:13 |