Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 24.11.2010, 16:31   #1
_Disa
 
Регистрация: 16.11.2010
Сообщений: 7
По умолчанию Алгоритм Дейкстры. Быстродействие

День добрый. Написал алгоритм Дейкстры и обнаружил что он весьма медленно работает на больших графах(число вершин больше 1000), вот код:
Код:
inline void Dijkstra ( int m[][], int N, int M, 
					   int start[], int end[] ) {
	register int i = 0, j = 0, k = 0, min = 0, minIndex = 0;
	int *minPathLength	= new  int[N];		// массив в конце содержащий минимальный путь
	bool *usedTops		= new bool[N];		// массив "использованости" вершин

	for ( j = 0; j < M; j++ ) {
		
		for ( i = 0; i < N; i++ ) {			// инициализация
			usedTops[i] = false;
			minPathLength[i] = m[start[j] - 1][i];
		}

		minPathLength[start[j] - 1] = 0;
		minIndex = start[j] - 1;
		
		// сам алгоритм
		for ( k = 0; k < N; k++ ) {
			for ( i = 0; i < N; i++ )
				if ( usedTops[i] == false && minPathLength[i] > minPathLength[minIndex] + m[minIndex][i] ) {
					 minPathLength[i] = minPathLength[minIndex] + m[minIndex][i];
				}
			min = INF;
			for ( i = 0; i < N; i++ )
				if ( usedTops[i] == false && min > minPathLength[i] ) {
					 min = minPathLength[i]; 
					 minIndex = i;
				}
			usedTops[minIndex] = true;
			if ( minIndex + 1 == end[j] ) {
				printf( "%i\n", minPathLength[minIndex] ); break;
			}
		}
	}

	delete[] minPathLength;
	delete[] usedTops;
}
m - матрица смежности, start и end - начала и концы искомых путей
Не подскажите как можно было бы улучшить алгоритм или следует применять алгоритм Йена?
_Disa вне форума Ответить с цитированием
Старый 24.11.2010, 16:57   #2
pproger
C++ hater
СтарожилДжуниор
 
Аватар для pproger
 
Регистрация: 19.07.2009
Сообщений: 3,336
По умолчанию

слишком много циклов и избыточная глубина. в классическом алгоритме дейкстры нет тройного вложенного цикла
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
pproger вне форума Ответить с цитированием
Старый 25.11.2010, 01:46   #3
_Disa
 
Регистрация: 16.11.2010
Сообщений: 7
По умолчанию

Ну классический алгоритм для двух вершин, разве не так? Для N нужно делать либо N переборок, либо искать наименьшего предка, если таковой уже найден, но могу быть и не прав, но что-то давно уже вожусь с этим. В начале написал флойда-уоршела, и тот после оптимизации стад давать даже лучший результат чем этот в своем нынешнем виде. Не могу понять почему, тк даже в случае тройных циклов Ф-У должен явно проигрывать, но по тестам получается что нет. Видимо придется провозиться еще не один день.
PS: не подскажите где можно прочитать подробно про алгоритм Йена? Есть мнение что его лучше брать при большом числе вершин.
_Disa вне форума Ответить с цитированием
Старый 10.12.2010, 14:30   #4
Kn793
Форумчанин
 
Регистрация: 20.06.2008
Сообщений: 125
По умолчанию

1) Вы для поиска вершины с минимальным расстоянием, используете обычный линейный поиск. Получим O(n^3) операций.
Нужно использовать приоритетную очередь, и список смежностей вместо матрицы. O(n^2 * log(n)).

2) Алгоритм Дейкстры рассчитан на поиск путей от одной вершины до всех. А запускать его n раз - слишком расточительно. Тут действительно нужно что-нибудь другое. Например Джонсона. Он хоть и имеет ту же асимптотику, но должен работать быстрее.
Kn793 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм Дейкстры (С++) 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