Логин: Пароль:

Спортивное программирование
в Красноярском крае


k_mihey
kormyshov


 


Перейти к профилю
Вернуться к ленте

Алгоритм Дейкстры

В общем, я тут немного подумал и наткнулся на следующую вещь.

Всем известно, что алгоритм Дейкстры состоит из трёх частей:

  • инициализация (выполняется 1 раз)
  • извлечь минимум (выполняется |V| раз)
  • релаксировать путь (выполняется |E| раз)

Простейшая реализация выполняет эти операции за O(|V|), O(|V|) и O(1) соответственно, что в итоге даёт O(|V|*|V| + |E|). И для плотных графов это оптимально, так как |E|~|V|*|V|.

Для разреженных графов применяют логарифмические структуры данных, которые позволяют выполнить операции за O(|V|), O(log|V|) и O(log|V|), что в итоге складывается в O((|V|+|E|)log|V|). И, когда |E| становится сильно меньше |V|*|V|, то это даёт свои плоды.

Это было известно всем. Но ведь есть ещё и другие структуры данных. Нет, я не предлагаю реализовывать Фибоначчиевы кучи. А вот SQRT-декомпозиция может нам помочь, потому что можно добиться следующих ассимптотик: O(sqrt(|V|)), O(sqrt(|V|)) и O(1). А в итоге это O(|V|^1.5 + E).

И вот в этом случае нужны ещё более сильные ограничения на |E|, чтобы применение кучи/сета было оправдано.

Например реализация с e-maxx (да не самая быстрая, но порядок сильно не меняется) для произвольного графа из 10000 вершин обгоняет корневую декомпозицию, если в графе не больше 0.2% рёбер. Если в ней избавиться от pair, то всё становится немного лучше, но всё равно не более 0.7%.

Приведу свой код, вдруг найдутся баги или оптимизации.

vector<int> sqrt_d;
int sqrt_n;
void sqrt_init(int v){
    sqrt_n = sqrt(N*0.3);
    sqrt_d.assign(N/sqrt_n+1, INF2);
    sqrt_d[v/sqrt_n] = 0;
}
int sqrt_get(vector<int> &d, vector<int> &f){
    int v = -1, i, t=0, c=1, dt;
    for(i=1;i<(int)sqrt_d.size();++i)
        if(sqrt_d[t] > sqrt_d[i]) t=i;
    int l = t*sqrt_n, r = min(l+sqrt_n, N);
    dt = sqrt_d[t];
    sqrt_d[t] = INF2;
    for(i=l; i<r; ++i){
        if(!f[i] && c && dt==d[i]) f[i]=1, c=0, v=i;
        if(!f[i]) sqrt_d[t] = min(sqrt_d[t], d[i]);
    }
    return v;
}
vector<int> Dijkstra_sqrt(int s){
    vector<int> d(N, INF2), f(N, 0);
    d[s] = 0;
    sqrt_init(s);
    int i, j, v, to, len;
    for(i=0;i<N;++i){
        v = sqrt_get(d, f);
        if(v<0 || d[v] >= INF2) break;
        for(j=0; j<(int)g[v].size(); ++j){
            to = g[v][j].first;
            len = g[v][j].second;
            if(d[v] + len < d[to]){
                d[to] = d[v] + len;
                if(sqrt_d[to/sqrt_n] > d[to])
                    sqrt_d[to/sqrt_n] = d[to];
            }
        }
    }
    return d;
}

Константа 0.3 в четвёртой строке была подобрана "на глазок", так как в sqrt_get в первом цикле одна операция сравнения, а во втором четыре (но там &&, поэтому не все будут проверяться), а таким приёмом мы избавимся от этого перекоса.

Буду рад комментариям.

2013-05-24


2013-05-27 demidenko
на 0 можешь поделить, ограничить единицей надо

2013-05-27 demidenko
в 16ой сделать --dt, и избавиться от c потом

2013-05-27 kormyshov
О, классно, спасибо

Система Orphus

(c) Copyright 2011-2014 Михаил Кормышов

kormyshov[dog]gmail.com