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

Необходимо найти кратчайшее расстояние от заданной вершины до всех остальных
Алгоритм работает на графах, не содержащих циклов отрицательного веса, петель и кратных рёбер.

Асимптотика O(n²).

Листинг C++

const int inf = 1e9;
void dij (int x, vector < vector < int > > &D, vector < int > &w, vector < int > &p)
{
    // initialization
    int i, j;
    int n = D.size ();
    vector < int > a (n, 0);
    w.assign (n, inf);
    p.assign (n, x);
    for (i = 0; i < n; ++ i)
            w[i] = D[x][i];
    a[x] = 1;
    w[x] = 0;
    p[x] = - 1;

    for (i = 0; i < n; ++ i)
    {
        // iMin - the closest not considered vertice
        int iMin = - 1, Min = inf;
        for (j = 0; j < n; ++ j)
            if (!a[j] && w[j] < Min)
            {
                iMin = j;
                Min = w[j];
            }

        if (iMin == - 1)
            return;
        a[iMin] = 1;

        // relaxation
        for (j = 0; j < n; ++ j)
            if (w[j] > w[iMin] + D[iMin][j])
            {
                w[j] = w[iMin] + D[iMin][j];
                p[j] = iMin;
            }
    }
}

18.05.2007, 17:47

По всем вопросам обращаться: rumterg@gmail.com