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

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

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

ПримерыПравить

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

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

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

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

АлгоритмПравить

Ниже приведена популярная и эффективная на специальных графах реализация модифицированного алгоритма Левита с сайта e-maxx.ru. Её отличие от «каноничной» версии заключается в добавлении элемента в очередь $\text{[math]}$ $\text{[math]}$ $M1$ в начало, а не в конец. Это позволяет достичь выигрыша на некоторых графах, однако приводит к экспоненциальному времени работы в худшем случае (см. раздел «Сложность»).

ОбозначенияПравить

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

КодПравить

Сразу стоит оговорить тот факт, что приведённый ниже код является не вполне работоспособным, так как не задана (каким-либо образом) структура графа. В итоге (по умолчанию) складывается ситуация, при которой имеется граф, состоящий из десяти (значение по умолчанию) изолированных вершин, а кратчайший путь ищется от вершины с индексом 1 до вершины с индексом 3 (значения по умолчанию).

#include <iostream>
// для структуры pair:
#include <utility>
#include <vector>
#include <deque>
// для значения INT_MAX:
#include <climits>
// для функции reverse:
#include <algorithm>

using namespace std;

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

const int INFINITY = INT_MAX;

// Значения по умолчанию для работы алгоритма (число вершин графа, индексы начальной и конечной вершин пути)
int defaultNumber = 10, 
    defaultStart = 1, 
    defaultFinish = 3;

int main()
{
    int numberOfVertices = defaultNumber,  
        startVertex = defaultStart, 
	finishVertex = defaultFinish;

    graph g (numberOfVertices);
    
	// Здесь считываем структуру графа (откуда-либо, например, из файла).
	// К слову, размерность и номера вершин для поиска скорее всего
	// необходимо получать из того же источника.

    vector<int> d (numberOfVertices, INFINITY);
    d[startVertex] = 0;
    
    vector<int> state (numberOfVertices, 2);
    state[startVertex] = 1;
    
    deque<int> q;
    q.push_back (startVertex);
    
    vector<int> p (numberOfVertices, -1);

    while (!q.empty())
    {
        int vertex = q.front();  
        q.pop_front();
        state[vertex] = 0;
        for (size_t i = 0; i < g[vertex].size(); ++i)
        {
            int to = g[vertex][i].first, 
                length = g[vertex][i].second;
            if (d[to] > d[vertex] + length)
            {
                d[to] = d[vertex] + length;
                if (state[to] == 2)
                    q.push_back (to);
                else if (state[to] == 0)
                    q.push_front (to);
                p[to] = vertex;
                state[to] = 1;
            }
        }
    }
    if (p[finishVertex] == -1)
    {
        cout << "No solution" << endl;
    }
    else
    {
        vector<int> path;
        for (int vertex = finishVertex; vertex != -1; vertex = p[vertex])
            path.push_back (vertex);
        reverse (path.begin(), path.end());
        for (size_t i = 0; i < path.size(); ++i)
            cout << path[i] + 1 << ' ';
    }

    // для запуска не из командной строки (чтобы была возможность увидеть результат)
    cin.get();
    return 0;
}

ОписаниеПравить

Пусть массив 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.

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

При неправильной реализации алгоритма, используя вместо очередей M1' и M1'' дек и добавляя вершины из M0 в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время^[2], так делать не рекомендуется. На реальных графах алгоритм зарекомендовал себя достаточно хорошо: время его работы $\text{[math]}$ $\text{[math]}$ $O(MN)$ ^[3].

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

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

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

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

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

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

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

См. такжеПравить

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

ПримечанияПравить

↑ Здесь частным случаем ориентированного графа являются неориентированный и смешанный («частично ориентированный») графы.
↑ Левит (модифицированный Ford-Bellman) с e-maxx.ru работает за экспоненту. — Codeforces (неопр.). Дата обращения: 22 июня 2013. Архивировано 6 июня 2012 года.
↑ Алгоритм Левита — Викиконспекты (неопр.). neerc.ifmo.ru. Дата обращения: 13 декабря 2018. Архивировано 24 ноября 2018 года.

СсылкиПравить

ЛитератураПравить

Б. Ю. Левит. Алгоритмы поиска кратчайших путей на графе. Труды института гидродинамики СО АН СССР. Сб. «Моделирование процессов управления». Вып. 4. Новосибирск. 1971. с. 1117—148
Б. Ю. Левит, В. Н. Лившиц. Нелинейные сетевые транспортные задачи, М. Транспорт. 1972. с.43-61
Dijkstra E. W. A note on two problems in connexion with graphs (англ.) // Numer. Math / F. Brezzi — Springer Science+Business Media, 1959. — Vol. 1, Iss. 1. — P. 269—271. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF01386390
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = 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.

[1] Здесь частным случаем ориентированного графа являются неориентированный и смешанный («частично ориентированный») графы.

[2] Левит (модифицированный Ford-Bellman) с e-maxx.ru работает за экспоненту. — Codeforces (неопр.). Дата обращения: 22 июня 2013. Архивировано 6 июня 2012 года.

[3] Алгоритм Левита — Викиконспекты (неопр.). neerc.ifmo.ru. Дата обращения: 13 декабря 2018. Архивировано 24 ноября 2018 года.

[1]

[2]

[3]