MAXimal

добавлено: 10 Jun 2008 19:39
редактировано: 2 Oct 2010 1:35

Алгоритм Левита нахождения кратчайших путей от заданной вершины до всех остальных вершин

Пусть дан граф с N вершинами и M ребрами, для каждого из которых указан его вес Li. Также дана стартовая вершина V0. Требуется найти кратчайшие пути от вершины V0 до всех остальных вершин.

Алгоритм Левита решает эту задачу весьма эффективно (по поводу асимптотики и скорости работы см. ниже).

Описание

Пусть массив D[1..N] будет содержать текущие кратчайшие длины путей, т.е. Di - это текущая длина кратчайшего пути от вершины V0 до вершины i. Изначально массив D заполнен значениями "бесконечность", кроме DV0 = 0. По окончании работы алгоритма этот массив будет содержать окончательные кратчайшие расстояния.

Пусть массив P[1..N] содержит текущих предков, т.е. Pi - это вершина, предшествующая вершине i в кратчайшем пути от вершины V0 до i. Так же как и массив D, массив P изменяется постепенно по ходу алгоритма и к концу его принимает окончательные значения.

 

Теперь собственно сам алгоритм Левита. На каждом шаге поддерживается три множества вершин:

  • M0 - вершины, расстояние до которых уже вычислено (но, возможно, не окончательно);
  • M1 - вершины, расстояние до которых вычисляется;
  • M2 - вершины, расстояние до которых ещё не вычислено.

Вершины в множестве M1 хранятся в виде двунаправленной очереди (deque).

 

Изначально все вершины помещаются в множество M2, кроме вершины V0, которая помещается в множество M1.

На каждом шаге алгоритма мы берём вершину из множества M1 (достаём верхний элемент из очереди). Пусть V - это выбранная вершина. Переводим эту вершину во множество M0. Затем просматриваем все рёбра, выходящие из этой вершины. Пусть T - это второй конец текущего ребра (т.е. не равный V), а L - это длина текущего ребра.

  • Если T принадлежит M2, то T переносим во множество M1 в конец очереди. DT полагаем равным DV + L.
  • Если T принадлежит M1, то пытаемся улучшить значение DT: DT = min (DT, DV + L). Сама вершина T никак не передвигается в очереди.
  • Если T принадлежит M0, и если DT можно улучшить (DT > DV + L), то улучшаем DT, а вершину T возвращаем в множество M1, помещая её в начало очереди.

Разумеется, при каждом обновлении массива D следует обновлять и значение в массиве P.

Подробности реализации

Создадим массив ID[1..N], в котором для каждой вершины будем хранить, какому множеству она принадлежит: 0 - если M2 (т.е. расстояние равно бесконечности), 1 - если M1 (т.е. вершина находится в очереди), и 2 - если M0 (некоторый путь уже был найден, расстояние меньше бесконечности).

Очередь обработки можно реализовать стандартной структурой данных deque. Однако есть более эффективный способ. Во-первых, очевидно, в очереди в любой момент времени будет храниться максимум N элементов. Но, во-вторых, мы можем добавлять элементы и в начало, и в конец очереди. Следовательно, мы можем организовать очередь на массиве размера N, однако нужно зациклить его. Т.е. делаем массив Q[1..N], указатели (int) на первый элемент QH и на элемент после последнего QT. Очередь пуста, когда QH == QT. Добавление в конец - просто запись в Q[QT] и увеличение QT на 1; если QT после этого вышел за пределы очереди (QT == N), то делаем QT = 0. Добавление в начало очереди - уменьшаем QH на 1, если она вышла за пределы очереди (QH == -1), то делаем QH = N-1.

Сам алгоритм реализуем в точности по описанию выше.

Асимптотика

Мне не известна более-менее хорошая асимптотическая оценка этого алгоритма. Я встречал только оценку O (N M) у похожего алгоритма.

Однако на практике алгоритма зарекомендовал себя очень хорошо: время его работы я оцениваю как O (M log N), хотя, повторюсь, это исключительно экспериментальная оценка.

Реализация

typedef pair<int,int> rib;
typedef vector < vector<rib> > graph;

const int inf = 1000*1000*1000;


int main()
{
	int n, v1, v2;
	graph g (n);

	... чтение графа ...

	vector<int> d (n, inf);
	d[v1] = 0;
	vector<int> id (n);
	deque<int> q;
	q.push_back (v1);
	vector<int> p (n, -1);

	while (!q.empty())
	{
		int v = q.front(),  q.pop_front();
		id[v] = 1;
		for (size_t i=0; i<g[v].size(); ++i)
		{
			int to = g[v][i].first, len = g[v][i].second;
			if (d[to] > d[v] + len)
			{
				d[to] = d[v] + len;
				if (id[to] == 0)
					q.push_back (to);
				else if (id[to] == 1)
					q.push_front (to);
				p[to] = v;
				id[to] = 1;
			}
		}
	}

	... вывод результата ...

}