MAXimal | |
добавлено: 10 Jun 2008 19:39 Содержание [скрыть] Алгоритм Левита нахождения кратчайших путей от заданной вершины до всех остальных вершинПусть дан граф с N вершинами и M ребрами, для каждого из которых указан его вес Li. Также дана стартовая вершина V0. Требуется найти кратчайшие пути от вершины V0 до всех остальных вершин. Алгоритм Левита решает эту задачу весьма эффективно (по поводу асимптотики и скорости работы см. ниже). ОписаниеПусть массив D[1..N] будет содержать текущие кратчайшие длины путей, т.е. Di - это текущая длина кратчайшего пути от вершины V0 до вершины i. Изначально массив D заполнен значениями "бесконечность", кроме DV0 = 0. По окончании работы алгоритма этот массив будет содержать окончательные кратчайшие расстояния. Пусть массив P[1..N] содержит текущих предков, т.е. Pi - это вершина, предшествующая вершине i в кратчайшем пути от вершины V0 до i. Так же как и массив D, массив P изменяется постепенно по ходу алгоритма и к концу его принимает окончательные значения.
Теперь собственно сам алгоритм Левита. На каждом шаге поддерживается три множества вершин:
Вершины в множестве M1 хранятся в виде двунаправленной очереди (deque).
Изначально все вершины помещаются в множество M2, кроме вершины V0, которая помещается в множество M1. На каждом шаге алгоритма мы берём вершину из множества M1 (достаём верхний элемент из очереди). Пусть V - это выбранная вершина. Переводим эту вершину во множество M0. Затем просматриваем все рёбра, выходящие из этой вершины. Пусть T - это второй конец текущего ребра (т.е. не равный V), а L - это длина текущего ребра.
Разумеется, при каждом обновлении массива 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; } } } ... вывод результата ... }
|