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

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

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

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

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