Форум программистов [Powered by Invision Power Board]

Код

#define GM 100000

// 
// k - сколько путей искать?
// s, dest - начальная и конечная вершины
// len - массив длин кратчайших путей
// p - массив. Каждый элемент его - массив вершин одного из кратчайших путей
bool Iens(int k, int u1, int u2, int maxw, int *length, int **p)
{
    int n;        // кол-во вершин в графе
    int *w, *Pt=NULL, *a;
    int i, j, m, m1, m2, mwg, l, lt, s, wg;
    int allweight=0;    // стоимость всех перелётов
    bool c;
    VERTEX v;
    vert V;

    if(k==0)
        return false;
    // Подсчитать кол-во вершин и заполнить матрицу w
    n = 0;
    for(edgelst::iterator i1 = graph.begin(); i1!=graph.end(); i1++)
    {
        v.x = i1->x1; v.y = i1->y1; v.num = i1->num1;
        if((V.insert(v)).second)
            ++n;
        v.x = i1->x2; v.y = i1->y2; v.num = i1->num2;
        if((V.insert(v)).second)
            ++n;
    }
    //a = new int[n*n];
    w = new int[n*n];
    Pt = new int[n];
    //p = new int*[k];
    for(i=0; i<k; i++)
    {
        //p[i] = new int[n];
        for(j=0; j<n; j++)
            p[i][j] = -1;
    }
    //length = new int[k];
    for(i=0; i<n*n; i++)
        w[i] = GM;
    for(edgelst::iterator i1 = graph.begin(); i1!=graph.end(); i1++)
    {
        w[i1->num1*n+i1->num2] = w[i1->num2*n+i1->num1] = i1->cost;
    }

    for(i=0; i<k; i++)
        length[i] = -1;

    l = 1;
    m = 0;
    while(l!=-1 && m<k)
    {
        FindShortestPath(n,w,u1,u2,l,wg,Pt);
        if(l!=-1)
        {
            length[m] = l;
            allweight += wg;
            if(allweight>maxw)
                l=-1;
            else
            {
                for(i=0; i<l; i++)
                    p[m][i] = Pt[i];
                // Удалить обработанные vertexes and edges из графа
                for(i=0; i<l-1; i++)
                    w[Pt[i]*n+Pt[i+1]] = w[Pt[i+1]*n+Pt[i]] = GM;
                for(i=1; i<l-1; i++)
                    for(j=0; j<n; j++)
                        w[Pt[i]*n+Pt[j]] = w[Pt[j]*n+Pt[i]] = GM;
            }
        }
        ++m;
    }
    if(l==-1)
        return false;

    delete[] Pt;
    delete[] w;

    return true;
}
// Find the shortest path in graph (Dejkstra's algorith)
// s = source; dest = destination
bool FindShortestPath(int n, int *w, int s, int dest, int& len, int& weight, int *Path)
{
    int length;
    int i, j, k, min, d1, t;
    int *d, *p, *m;
    vert V;    // Additional var.

    //Path = new int[n];
    for(i=0; i<n; i++)
        Path[i] = -1;
    d = new int[n];
    p = new int[n];
    m = new int[n];

    length = 0;
    i = 0;
    do{
        d[i] =GM;
        p[i] = 0;
        m[i] = 0;
        ++i;
    }while(i<n);
    d[s] = 0;
    m[s] = 1;
    t = s;
    while(!length)
    {
        i = 0;
        do{
            if(w[t*n+i]<GM)
            {
                d1 = d[t] + w[t*n+i];
                if(d[i]>d1)
                {
                    d[i] = d1;
                    p[i] = t;
                }
            }
            ++i;
        }while(i<n);
        min = GM;
        i = 0;
        k = -1;
        do{
            if(m[i]==0)
            {
                if(d[i]<min)
                {
                    min = d[i];
                    k = i;
                }
            }
            ++i;
        }while(i<n);
        if(k==-1)
        {
            length = -1;
        }
        else
        {
            m[k] = i;
            t = k;
            if(t==dest)
            {
                length = 1;
            }
        }
    }
    if(length==1)
    {
        Path[0] = dest;
        ++length;
        j = dest;
        do{
            Path[length-1] = p[j];
            j = p[j];
            ++length;
        }while(j!=s);
        i = 0;
        j = n-1;
        k = !(length%2) ? length/2 : length/2 + 1;
        do{
            t = Path[i];
            Path[i] = Path[j];
            Path[j] = t;
            ++i; --j;
        }while(i<=k);
        --length;
        while(Path[0]==-1)
        {
            for(i=0; i<n-1; i++)
                Path[i] = Path[i+1];
        }
    }
    weight = d[dest];
    len = length;

    delete[] d;
    delete[] p;
    delete[] m;

    return length>=0;
}