Как стать автором
Обновить

Комментарии 35

НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Да, согласен. Постарался поправить формулировку
Оказалось, что на самом деле очень легко писать Дейкстру за O(n * log(n) + m * log(n))!

Откуда вы взяли лишнее log(n) при m? Стандартная сложность этого алгоритма при использовании кучи — O(m + n* log(n)).

Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.

На интуитивном уровне понятно, что если до какой-то вершины путь сейчас минимальный, то еще меньше сделать его мы не сможем.

А вот и нет, интуитивно понятно, но неверно. Точнее, верно только в том случае, если вы соблюдаете ограничение применимости этого алгоритма, про которое в посте ни слова.
Откуда вы взяли лишнее log(n) при m? Стандартная сложность этого алгоритма при использовании кучи — O(m + n* log(n)).

Если использовать фибоначчиеву кучу, то да. При использовании обычной кучи, асимптотика именно такая, как я показал.

А вот и нет, интуитивно понятно, но неверно. Точнее, верно только в том случае, если вы соблюдаете ограничение применимости этого алгоритма, про которое в посте ни слова.

Согласен, это верно только при не отрицательных весах ребер, сейчас допишу об этом в посте.
А что такое «обычная куча»? Какие у нее стоимости операций?
Будем считать, что на верхушке кучи лежит минимум, тогда O(log(n)) на добавление, O(log(n)) на удаление минимума, O(1) на поиск минимума
Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.

Не согласен. Кучу писать совсем не сложно.
Продемонстрируете?
Вы либо троллите, либо действительно не знаете. Буду исходить из второго и добавлю реализацию кучи в пост.
Ваша реализация больше по объему, чем реализация самого алгоритма. Так, в общем-то, и должно бы быть; логика там тоже сложнее внутри (особенно когда вы все-таки добавите произвольный доступ).
Собственно, вот полная реализация:

Код
struct XVert{
	int backidx;
	int backway;
	double dist;
};

struct Edge{
	int idx;
	double dist;
};

struct Vert{
	int NEdges;
	Edge *Edges;
};

struct Graph{
	int NV;
	Vert *Verts;
};

double Dejkstra(Graph *G,int Start,int End){
	int NV=G->NV;
	int LQ=NV;
	XVert *Verts=new XVert[NV];
	Edge *Que=new Edge[NV];
	for(int i=0;i<NV;i++){
		int j=(i==0 || i==Start) ? Start-i : i;
		Verts[i].dist=100;
		Verts[i].backidx=j;
		Verts[i].backway=-1;
		Que[i].dist=100;
		Que[i].idx=j;
	}
	Verts[Start].dist=Que[0].dist=0;
	Verts[Start].backway=-1;

	for(;;){
		Edge top=Que[0];
		int v0=top.idx;
		if(top.idx==End) break;
		Edge btm=Que[--LQ];
		int a=0,b;
		while((b=2*a+2)<=LQ){
			if(b==LQ || Que[b].dist>Que[b-1].dist) b--;
			if(Que[b].dist>=btm.dist) break;
			Que[a]=Que[b];
			Verts[Que[a].idx].backidx=a;
			a=b;
		}
		Que[a]=btm;
		Verts[btm.idx].backidx=a;
		Verts[top.idx].backidx=-1;
		for(int k=0;k<G->Verts[v0].NEdges;k++){
			Edge *e=G->Verts[v0].Edges+k;
			double d=top.dist+e->dist;
			int h=Verts[e->idx].backidx;
			if(h<0 || d>=Verts[e->idx].dist) continue;
			Verts[e->idx].dist=d;
			Verts[e->idx].backway=v0;
			Edge current=Que[h];
			while(h>0){
				int h1=(h-1)/2;
				if(Que[h1].dist<d) break;
				Que[h]=Que[h1];
				Verts[Que[h].idx].backidx=h;
				h=h1;
			}
			current.dist=d;
			Que[h]=current;
			Verts[e->idx].backidx=h;
		}
	}
	double res=Que[0].dist;
	delete[] Verts;
	delete[] Que;
	return res;
}


Если не считать 13 строк описаний структур, то вся функция занимает 50 строк, из них 30 — на приоритетную очередь (с обратными ссылками и возможностью замены весов), 20 — на остальной алгоритм. Так что действительно, не так уж сложно. Тем более, что максимальная длина в данном случае заранее известна. Конечно, если new[] считать частью фреймворка, то жизнь будет несколько сложнее, но в ситуациях, когда нет malloc, у нас максимальные размеры структур фиксированы. В крайнем случае, два массива можно будет захватить на стеке.
Там в двух местах осталось dist=100 (со времени отладки) — заметил слишком поздно, его надо заменить на максимальное значение double.
Пойнт не столько в размере, сколько в «концептуальной сложности». По моему опыту, написать кучу хотя бы на основе бинарного дерева сложнее, чем просто реализовать алгоритм Дийкстры — больше неочевидных мест, где можно ошибиться.

(ну и будем честными, я все-таки не понял из вашего кода, как именно вы делаете замену веса, точнее — поиск элемента для замены, но это сказывается мое неумение читать terse code)
Поле XVert.backidx — текущий индекс данной вершины в массиве, на котором реализована куча (он меняется при каждом перемещении элемента кучи вверх или вниз). Поэтому, при замене веса я сразу беру индекс в массиве кучи, и начинаю двигать элемент с этим индексом вверх (если надо).
Операции добавления вершины в кучу мне не понадобилось вообще — куча сразу создаётся со всеми вершинами, имеющими максимальный вес (кроме стартовой, у которой вес равен нулю — она кладётся в начало массива). Это приведёт к некоторой потере эффективности в ситуации, когда надо найти путь между очень близкими вершинами в очень большом графе (на первый вход в вершины потратится k*log(V) операций вместо k*log(k), где k — число вершин, которые нужно просмотреть), но код получается компактнее.
Спасибо.
Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.

Реализация приоритетной очереди — 25-30 строк, ненамного больше остальной части алгоритма.

Откуда вы взяли лишнее log(n) при m?

Заметим, что в статье ни разу не говорилось, что такое n и m. Можно догадаться, что одно из них — вершины, а другое — рёбра, но что есть что — непонятно.
При данной реализации — когда вершины со старыми весами остаются в куче до тех пор, пока не дойдёт очередь до их старого веса — размер кучи может доходить до O(E), где E — число рёбер. Например, так будет для графа с вершинами 1..V, где d(m,n)=2*abs(m-n)-1, и мы ищем путь от 1 до n. Каждый новый улучшенный экземпляр вершины придётся положить в кучу, на это потребуется до E*log(E) операций.
«Традиционно» n = |V|, m = |E|.
Кстати, а где в вашем алгоритме замена весов ранее вставленных вершин? Иными словами, если на шаге один в кучу добавлена вершина u с весом 15, а на шаге три в кучу добавлена эта же вершина с весом 3 — сколько записей о вершине u будет в куче?
В посте описано. Нужно не проводить релаксацию, если из кучи достали неактуальный путь.
При такой реализации, как уже написано выше, вы получаете высоту кучи в O(log|E|), что для полного графа равно O(log(|V|2) (это в расчете на то, что дублирующиеся ребра вы оптимизируете на предварительном этапе), против O(log(|V|) в стандартной реализации.
O(log|E|), что для полного графа равно O(log(|V|^2))… против O(log(|V|)

Хорошая попытка :)

К счастью, O(log (|V|^2)) = O(2*log |V|) = O(log |V|), так что мы теряем не более, чем константу (а может быть, и выигрываем — ведь нам не нужно поддерживать функцию уменьшения веса).
Память на кучу проигрываем, причём сильно — это верно. Если граф у нас не хранится в памяти, а как-то вычисляется, то это может быть плохо.
O(log (|V|^2)) = O(2*log |V|) = O(log |V|),

Если так считать, то можно ограничиться стэнфордским определением асимптотики алгоритма в O(|E| log |V|) и не мучиться разницей между разными реализациями кучи.

(собственно, наивная функция уменьшения веса — 2*log(n), потому что сводится к удалению и вставке, оба из которых реализуемы на двоичной куче за log(n)),
1) Между O(2*log(|V|) и O(log(|E|*log(|V|) есть небольшая разница: 2 это константа, а log(|E|) — нет. Определение O(f(x)) даётся так, что изменение f(x) в константу раз на результат не влияет. А если f(x) умножается на величину, зависящую от x, то класс алгоритмов и их асимптотика может измениться.
2) Операции «удаление произвольного элемента» в наивной реализации кучи не предусмотрено — она бы потребовала просмотра всей кучи. А если мы умеем быстро искать элемент, то изменить его вес так же просто, как добавить новый: ведь добавление элемента в кучу фактически реализуется как добавление его в конец массива с бесконечным весом плюс последующее уменьшение веса.
Между O(2*log(|V|) и O(log(|E|*log(|V|)

А откуда вы взяли log(|E|*log(|V|))?

А если мы умеем быстро искать элемент, то изменить его вес так же просто, как добавить новый

Не совсем — нам надо не забыть восстановить инварианты по отношению к тому месту, откуда мы «вытаскиваем» элемент. Это не сложно, но тоже требует аккуратности. Собственно, здесь и накапливается сложность (не алгоритмическая) реализации кучи.
Когда мы добавляем новый элемент (или удаляем минимум), то при реализации через массив у нас меняется положение части элементов в массиве. И для них всё равно приходится отслеживать изменение информации для поиска. Если вы знаете способ реализовать кучу с удалением произвольного элемента, в котором добавление операции изменения веса (отличной от удаления+вставки) приводит к заметному усложнению реализации — было бы интересно взглянуть.
Ну, как я это в свое время реализовывал: при вставке мы получаем bubble-up. При снятии верха — bubble-down. При вытаскивании элемента из середины — не важно, для удаления или для перевесовки, — нужно сделать либо то, либо другое, в зависимости от отношения весов элементов. С моей точки зрения (ну и банально по тому, сколько времени я потратил на отлов багов) вот это «то либо другое» и есть усложнение реализации.

Но я, правда, говорю про generic heap, который просто структура данных, отвязанная от алгоритма.
При вытаскивании элемента из середины — не важно, для удаления или для перевесовки, — нужно сделать либо то, либо другое, в зависимости от отношения весов элементов.


Дешевле всего вызвать и то и другое. По количеству операций получается не больше операций чем если проверять соотношение весов и вычислять направление «всплытия»
«И то и другое» — вы имеете в виду удаление и последующую вставку с новым весом? В случае бинарной кучи это безумно дорого. Обычно при уменьшении веса объект либо не надо двигать вообще (он уже тяжелее своего родителя), либо его надо переставить на 1-2 ступеньки вверх. И сравнивать на каждом этапе только с родителем. А удаление+вставка — это надо сначала утопить самый тяжелый объект, вставленный на место удалённого (2*log(K) сравнений, где K — положение нашего объекта, считая снизу), а потом — всплыть наш объект с самого последнего места (ещё не менее log(K) сравнений). Если мы уменьшаем вес объекта, близкого к вершине, то потребуется до 3*log(N) сравнений (и 2*log(N) перемещений), когда хватило бы совсем маленьких значений.
И то и другое — это вызвать метод всплытия а потом метод утопления. Потому что когда вы удаляете объект из середины, вы меняете удаляемый объект с последним элементом, после этого элемент нужно расположить на нужном уровне. И этот уровень может быть как выше так и ниже. При этом один из вызовов в данном случае делает только проверку что перемещать объект не надо и выходит.
Согласен. Редкая ситуация, но может случиться.
На самом деле эта ситуация не так редка как может показаться. Она может возникнуть, когда последний элемент находится в другой ветке относительно элемента который мы удаляем.
Собственно, когда я реализовывал этот самый алгоритм Дийкстры, я при реализации «кучи» сделал только утопление, считая, что если я поменял с последним элементом, этот элемент должен потонуть обратно вниз. Потом сутки пытался понять почему у меня с вероятностью 70% получается неверный результат.
Собственно, когда я реализовывал этот самый алгоритм Дийкстры, я при реализации «кучи» сделал только утопление, считая, что если я поменял с последним элементом, этот элемент должен потонуть обратно вниз. Потом сутки пытался понять почему у меня с вероятностью 70% получается неверный результат.

+1

Собственно, именно поэтому я говорю, что в реализации алгоритма Дийкстры с кучей куча — самое сложное место.
В статье есть ссылки на e-maxx, так что автор знает о существовании этого замечательного сайта.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории