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

Алгоритм Левіта (Levit's algorithm) — алгоритм на графах, знаходить найкоротшу відстань від однієї з вершин графу до всіх інших. Алгоритм також працює для графів з ребрами від'ємної ваги. Алгоритм широко застосовується в програмуванні і технологіях.

Формулювання завдання

Приклади

Варіант 1. Дана мережа автомобільних доріг, що з'єднують міста Львівської області. Деякі дороги односторонні. Знайти найкоротші шляхи від міста Львів до кожного міста області (якщо рухатися можна тільки по дорогах).

Варіант 2. Є деяка кількість авіарейсів між містами світу, для кожного відома вартість. Вартість перельоту з A в B може бути не дорівнює вартості перельоту з B в A. Знайти маршрут мінімальної вартості (можливо, з пересадками) від Копенгагена до Барнаула.

Формальне визначення

Дано зважений орієнтований граф $G(V,E)$ без петель. Знайти найкоротші шляхи від деякої вершини $a$ графу $G$ до всіх інших вершин цього графу.

Алгоритм

Нижче приведена популярна і ефективна на спеціальних графах реалізація модифікованого алгоритму Левіта. Її відмінність від «канонічної» версії полягає в додаванні елемента в чергу $M1$ в початок, а не кінець. Це дозволяє досягти виграшу на деяких графах, проте призводить до експоненціального часу роботи в гіршому випадку (див. Розділ «Складність»).

Позначення

• $N$ — множина вершин графу
• $M$ — множина ребер графу
• $g[ij]$ — вага (довжина) ребра $ij$
• $s$ — вершина, відстані від якої шукаються, тобто стартова вершина
• $d[i]$ — це поточна довжина найкоротшого шляху від вершини $s$ до вершини $i$
• $p[i]$ — це вершина, попередня вершині $i$ в найкоротшому шляху від вершини $s$ до $i$.
• $M0$ — вершини, відстань до яких вже обчислено (але, можливо, не остаточно);
• $M1$ — вершини, відстань до яких обчислюється;
• $M2$ — вершини, відстань до яких ще не обчислено.
• $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> rib;
typedef vector < vector<rib> > 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 в початок дека, алгоритм в гіршому випадку буде працювати за експоненціальне час, так робити не рекомендується. На реальних графах алгоритм зарекомендував себе досить добре: час його роботи $O(MN)$.

Порівняння алгоритмів Дейкстри і Левіта

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

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

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

Друга складність серйозніша: при від'ємних довжинах в графі можуть знайтися контури з від'ємною сумою довжин дуг (назвемо такі контури «від'ємними»). Додавання до шляху від'ємного контуру зменшує значення цільової функції, і чим більше обходів від'ємного контуру ми додамо, тим «краще». Позбутися від нескінченного зменшення мінімуму просто так неможливо, але є два виходи із скрутного становища (звичайно ж, вибір виходу залежить не від нас, а від розв'язуваної практичного завдання).

• Заборонити включення в шлях контурів, тобто розглядати тільки прості шляхи, але така заборона робить задачу дуже складною.
• У разі негативних контурів вважати, що завдання рішення не має, і обмежитися рішенням задачі у випадках, коли від'ємних контурів немає. У цьому випадку метод Левіта дасть необхідну оптимальне рішення, а при деякій модифікації дозволить «відловлювати» від'ємні контури.

Література

• Б. Ю. Левит. Алгоритмы поиска кратчайших путей на графе. Труды института гидродинамики СО АН СССР. Сб. «Моделирование процессов управления». Вып. 4. Новосибирск. 1971. с. 1117—148
• Б. Ю. Левит, В. Н. Лившиц. Нелинейные сетевые транспортные задачи, М. Транспорт. 1972. с.43-61