Путь максимальной длины в графе

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

Задача является NP-полной, поэтому используем перебор с возвратом.

Листинг C++

// maximum in vector < int >
int maximum (vector < int > &a)
{
    int m = - 1e9;
    for (int i = 0; i < a.size (); ++ i)
        m = max (m, a[i]);
    return m;
}
// maximal way from given vertices
void max_way_from_one (int x, vector < vector < int > > &D,
              vector < int > &w, vector < int > &p, vector < int > &is)
{
    is[x] = 1;

    for (int i = 0; i < D.size (); ++ i)
        if (!is[i] && D[x][i])
        {
            vector < int > wt = w;
            vector < int > pt = p;
            w[i] = w[x] + D[x][i];
            p[i] = x;

            // recursion for next
            max_way_from_one (i, D, w, p, is);

            if (maximum (wt) > maximum (w))
            {
                w = wt;
                p = pt;
            }
        }

    is[x] = 0;
}
// maximal way in the graf whose(way) incluse vertice only once
void max_way (vector < vector < int > > &D,
              vector < int > &w, vector < int > &p)
{
    int i;
    int n = D.size ();
    int Max = - 1;

    for (i = 0; i < n; ++ i)
    {
        vector < int > wt (n, 0);
        vector < int > pt (n, - 1);
        vector < int > is (n, 0);

        max_way_from_one (i, D, wt, pt, is);

        int m = maximum (wt);

        if (m > Max)
        {
            Max = m;
            w = wt;
            p = pt;
        }
    }
}

19.05.2007, 14:50

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