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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

Примеры

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

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

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

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

Алгоритм

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

Обозначения

  • [math]\displaystyle{ N }[/math] — множество вершин графа
  • [math]\displaystyle{ M }[/math] — множество ребер графа
  • [math]\displaystyle{ g[ij] }[/math] — вес (длина) ребра [math]\displaystyle{ ij }[/math]
  • [math]\displaystyle{ s }[/math] — вершина, расстояния от которой ищутся, то есть стартовая вершина.
  • [math]\displaystyle{ d[i] }[/math] — это текущая длина кратчайшего пути от вершины [math]\displaystyle{ s }[/math] до вершины [math]\displaystyle{ i }[/math]
  • [math]\displaystyle{ p[i] }[/math] — это вершина, предшествующая вершине [math]\displaystyle{ i }[/math] в кратчайшем пути от вершины [math]\displaystyle{ s }[/math] до [math]\displaystyle{ i }[/math].
  • [math]\displaystyle{ M0 }[/math] — вершины, расстояние до которых уже вычислено (но, возможно, не окончательно);
  • [math]\displaystyle{ M1 }[/math] — вершины, расстояние до которых вычисляется;
  • [math]\displaystyle{ M2 }[/math] — вершины, расстояние до которых ещё не вычислено.
  • [math]\displaystyle{ state[i] }[/math] — хранит номер множества, к которому относится вершина 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], так делать не рекомендуется. На реальных графах алгоритм зарекомендовал себя достаточно хорошо: время его работы [math]\displaystyle{ O (M N) }[/math][3].

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

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

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

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

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

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

См. также

Примечания

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

Ссылки

Литература

  • Б. Ю. Левит. Алгоритмы поиска кратчайших путей на графе. Труды института гидродинамики СО АН СССР. Сб. «Моделирование процессов управления». Вып. 4. Новосибирск. 1971. с. 1117—148
  • Б. Ю. Левит, В. Н. Лившиц. Нелинейные сетевые транспортные задачи, М. Транспорт. 1972. с.43-61
  • Шаблон:Source
  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = 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.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Алгоритм_Левита&oldid=5902337