VPF::Прошу помочь - Форум программистов

Dars2

Дата 21.5.2006, 10:57 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 21.5.2006

Репутация: нет
Всего: нет

Следующая проблема:

Нужен алгоритм нахождения критического (длиннейшего) пути в орграфе от самой первой вершины до последней (от 0 до m-1), представленного в виде матрицы m x m типа:

Код


{
{-Inf, 0,-Inf, -Inf, 0, -Inf, -Inf, 0, -Inf, -Inf, -Inf},
{-Inf, -Inf,10, -Inf, -Inf, -Inf, -Inf, -Inf,10, -Inf, -Inf},
{-Inf, -Inf,-Inf, 8,8, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 4, 4},
{-Inf, -Inf,-Inf, -Inf, -Inf, 5, -Inf, -Inf, -Inf, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, 5, -Inf, -Inf, -Inf, -Inf},
{-Inf,6,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 6},
{-Inf, -Inf,4, -Inf, -Inf, -Inf, -Inf, -Inf, 4, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 7, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf,3, -Inf, -Inf, -Inf, -Inf, 3},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf}}

Вышеприведенный пример представляет собой ориентированный граф, внутри которого есть циклы (цикл путь: 2-3-5-6-7-2). Поэтому стандартный алгоритм нахождения критического пути не работает. Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины. На данный момент есть следующий код, но он не похоже не работает при зацикливании:

Код


void Topological_Sort () //Процедура топологической сортировки
{
    int Children[n];
    int index=n-1;
    {for (int v=0; v<n; v++) Children[v]=0;}
    {for (int v=0; v<n; v++)
        for (int v2=0; v2<n; v2++)
            if (graph[v][v2]!=Inf && v2!=v) Children[v]++;}

    bool found;
    do {
        found=false;
        for (int v=0; v<n; v++)
            if (!Children[v]) {
                for (int p=0; p<n; p++) if (graph[p][v]!=Inf) Children[p]--;
                Children[v]=1;
                Order[index--]=v;
                found=true;
                break;
            }
    } while (found);
}

int dist(int s, int d) //Процедура для подсчета длины длиннейшего пути в графе
//Мы принимаем, что есть только одна начальная и одна конечная вершина,  и нам необходимо найти длиннейший путь
{
    //1 - Делаем топологическую сортировку множества вершин: V->Order[]
    Topological_Sort();
    //Первая будет все время в Order[0], тогда как последняя в Order[n-1]

    //2 - Используем техничку динамического программирования
    //  Rule: Dist[d]=max{Dist[v]+graph[v][d], (v,d) in E}
    int Dist[n];

    int v;
    {for (int v=0; v<n; v++) Dist[v]=graph[s][v];}
    Dist[s]=0;
    for (int i=0; i<n; i++) {
        v=Order[i];
        for (int pred=0; pred<n; pred++) if (graph[pred][v]!=Inf)
            if (Dist[pred]+graph[pred][v]>Dist[v]) Dist[v]=Dist[pred]+graph[pred][v];
    }

    return Dist[d]; //Возвращаем последнею величину v (=Order[n-1]) 
}

Возможно, как-то можно внести изменение в этот код, чтобы решалось нормально. Помогите плиз!!!!

Код

Это сообщение отредактировал(а) Dars2 - 21.5.2006, 10:58

Dars2

Дата 24.5.2006, 16:57 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 21.5.2006

Репутация: нет
Всего: нет

Неужели нет решения????

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »