Алгоритм Левита

Алгоритмы поиска на графах
A* B* Алгоритм Беллмана — Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда — Уоршелла

Алгори́тм Левита (Levit’s algorithm) — алгоритм на графах, находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм также работает для графов с рёбрами отрицательного веса. Алгоритм широко применяется в программировании и технологиях.

Формулировка задачи

Примеры

Вариант 1. Дана сеть автомобильных дорог, соединяющих города Московской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Москва до каждого города области (если двигаться можно только по дорогам).

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Формальное определение

Дан взвешенный ориентированный^[1] граф $G(V, E)$ без петель и дуг отрицательного веса^[2]. Найти кратчайшие пути от некоторой вершины $a$ графа $G$ до всех остальных вершин этого графа.

Алгоритм

Обозначения

• $N$ — множество вершин графа
• $M$ — множество ребер графа
• $g[ij]$ — вес (длина) ребра $ij$
• $s$ — вершина, расстояния от которой ищутся, то есть стартовая вершина.
• $d[i]$ — это текущая длина кратчайшего пути от вершины $s$ до вершины $i$
• $p[i]$ — это вершина, предшествующая вершине $i$ в кратчайшем пути от вершины $s$ до $i$.
• $M0$ - вершины, расстояние до которых уже вычислено (но, возможно, не окончательно);
• $M1$ - вершины, расстояние до которых вычисляется;
• $M2$ - вершины, расстояние до которых ещё не вычислено.
• $state[i]$ - хранит номер множества, к которому относится вершина i.

[Код]

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> state (n, 2);
   state[v1] = 1;
   deque<int> q;
   q.push_back (v1);
   vector<int> p (n, -1);

   while (!q.empty())
   {
       int v = q.front(),  q.pop_front();
       state[v] = 0;
       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 (state[to] == 2)
                   q.push_back (to);
               else if (state[to] == 0)
                   q.push_front (to);
               p[to] = v;
               state[to] = 1;
           }
       }
   }

   if (p[v2] == -1)
       cout << "No solution";
   else
   {
       vector<int> path;
       for (int v = v2; v != -1; v = p[v])
           path.push_back (v);
       reverse (path.begin(), path.end());

       for (unsigned i=0; i<path.size(); ++i)
           cout << path[i]+1 << ' ';
   }

}

Описание

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

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

Изначально все вершины помещаются в множество 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.

Сложность алгоритма

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

Сравнение алгоритмов Дейкстры и Левита

В сравнении с методом Дейкстры метод Левита проигрывает на том, что некоторые вершины приходится обрабатывать повторно, а выигрывает на более простых алгоритмах включения и исключения вершин из множества М1. Эксперименты показывают, что для графов с «геометрическим» происхождением, т.е. для графов, построенных на основе транспортных сетей и реальных расстояний, метод Левита оказывается наиболее быстрым. Он выигрывает и по размеру программы.

Метод Левита обладает еще и тем преимуществом перед методом Дейкстры, что он применим в случае отрицательных длин дуг (ведь «длина дуги» - это просто название, которое дает нам полезные ассоциации с реальностью). Если считать, что значения l(u) не обязательно положительны, решение задачи о кратчайшем пути значительно усложняется.

Первая трудность в том, что теряется простое правило метода Дейкстры для определения окончательности вычисленного расстояния до конкретной дуги. Эта трудность, как мы увидим дальше, обходится, хотя и с некоторой потерей эффективности метода (приходится проверять все дуги, ведущие в данную вершину).

Вторая трудность серьезнее: при отрицательных длинах в графе могут найтись контуры с отрицательной суммой длин дуг (назовем такие контуры «отрицательными»). Прибавление к пути отрицательного контура уменьшает значение целевой функции, и чем больше обходов отрицательного контура мы прибавим, тем «лучше». Избавится от бесконечного убывания минимума просто так невозможно, но есть два выхода из трудного положения (конечно же, выбор выхода зависит не от нас, а от решаемой практической задачи).

• Запретить включение в путь контуров, т.е. рассматривать только простые пути, но такой запрет делает задачу очень сложной.

• В случае отрицательных контуров считать, что задача решения не имеет, и ограничится решением задачи в случаях, когда отрицательных контуров нет. В этом случае метод Левита даст требуемое оптимальное решение, а при некоторой модификации позволит «отлавливать» отрицательные контуры.

См. также

• Алгоритм Беллмана — Форда — решение той же задачи, если граф может содержать и рёбра отрицательного веса
• Алгоритм Флойда — Уоршелла — поиск кратчайших расстояний между всеми парами вершин
• Алгоритм Джонсона
• Алгоритм Дейкстры — решение той же задачи, но другим способом.

Примечания

1. ↑ Здесь частным случаем ориентированного графа являются неориентированный и смешенный («частично ориентированный») графы.
2. ↑ Для графа с отрицательными весами применяется более общий алгоритм — Алгоритм Дейкстры с потенциалами

Ссылки

• Алгоритм Левита нахождения кратчайших путей от заданной вершины до всех остальных вершин
• Реализация алгоритмов Дейкстры и Левита
• C. Анисимов. Как построить кратчайший маршрут между двумя точками.

Литература

• E. W. Dijkstra. A note on two problems in connexion with graphs. // Numerische Mathematik. V. 1 (1959), P. 269-271
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
• Романовский И.В. Дискретный анализ: Учебное пособие для студентов, специализирующихся на прикладной математике и информатике.. — 3-е изд. — СПб.: Невский Диалект, 2003. — С. 221-222.
• Ананий В. Левитин Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 189—195. — ISBN 0-201-74395-7