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

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

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

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

Используем set для хранения нерассмотренных вершин в неубывающем порядке.
Асимптотика O(MlogN).

Листинг C++

const int inf = 1e9;
class edge
{
public :
    int v, w;
    edge (int _v, int _w) : v (_v), w (_w) {};
};
bool operator < (edge a, edge b) { return a.w < b.w || (a.w == b.w && a.v < b.v); }
bool operator == (edge a, edge b) { return a.w == b.w && a.v == b.v; }

void dij_sparse (int x, vector < vector < edge > > &e, vector < int > &w, vector < int > &p)
{
    int i, j;
    int n = e.size ();
    vector < int > a (n, 0);
    w.assign (n, inf);
    p.assign (n, - 1);
    w[x] = 0;    
    set < edge > u;
    for (i = 0; i < n; ++ i)
        u.insert (edge (i, i == x ? 0 : inf));
    
    for (i = 0; i < n; ++ i)
    {
        int v = (* u.begin ()).v;
        u.erase (u.begin ());
        a[v] = 1;
        
        for (j = 0; j < e[v].size (); ++ j)
        {
            int to = e[v][j].v;
            if (!a[to] && w[to] > w[v] + e[v][j].w)
            {
                u.erase (u.find (edge (to, w[to])));
                w[to] = w[v] + e[v][j].w;
                p[to] = v;
                u.insert (edge (to, w[to]));
            }
        }
    }
}

26.08.2008, 14:24