Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

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

Необходимо найти кратчайшие расстояния в графе от заданной вершины до всех остальных

В реализации необходимо использовать двунаправленную очередь, рекомендую писать её самому, а не использовать deque < int >, тогда выйгрыш во времени будет существенный.

Асимптотика O(NM).
На практике алгоритм работает гораздо быстрее, приближаясь к O(M).


Листинг C++

const int inf = (int)1e9;
class edge
{
public :
    int v, w;
    edge (int _v = 0, int _w = 0) : v (_v), w (_w) {};
};
void levit (int x, vector < vector < edge > > &e,
            vector < int > &w, vector < int > &p)
{
    int i, j;
    int n = e.size ();

    w.assign (n, inf);
    p.assign (n, - 1);
    w[x] = 0;

    vector < int > id (n, 2);
    deque < int > m1;
    id[x] = 1;
    m1.push_back (x);

    while (m1.size ())
    {
        int v = m1.front ();
        m1.pop_front ();
        id[v] = 0;

        for (i = 0; i < e[v].size (); ++ i)
        {
            int to = e[v][i].v;
            int l = e[v][i].w;

            if (id[to] == 2)
            {
                id[to] = 1;
                m1.push_back (to);
            }
            if (id[to] == 0 && w[to] > w[v] + l)
            {
                id[to] = 1;
                m1.push_front (to);
            }

            if (w[to] > w[v] + l)
            {
                w[to] = w[v] + l;
                p[to] = v;
            }
        }
    }
}

19.05.2007, 14:50