Изчисляване на критичния път на DAG в C++

Правя изчислението на критичния път за DAG на изображението, според този алгоритъм за друга публикация. Моят учител изисква масивът да бъде внедрен, аз опростявам формулировката за домашна работа, проста графика, реализирана чрез масиви.

въведете описание на изображението тук

Това е моят код, в който имам 3 масива v, u и d, представляващи началния възел на ръбовете, крайния възел на ръбовете и разстоянието между всяка двойка върхове, както е показано на снимката по-горе. в графиката на изображението продължителността на проекта е равна на 25, съответстваща на сумата от разстояния от критичния път.

Моят код не успява да направи правилно изчислението на разстоянията според псевдокода на тази връзка

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

int main (){


    int numberVertex=6; //number  of vertex
    int numberActivities=9;//number of edges
    int i, j;

    /*vertices are of the form (v, u) */
    //indegree of each vertex (that is, count the number of edges entering them) 
    int indegree [6]={0,0,0,0,0,0};

    int v[9]={0,0,1,1,2,4,3,3,3};//array v represent the starting vertex of de edge 
    int u[9]={1,2,2,3,4,5,4,5,5};//array u represent the coming vertex of de edge 
    int d[9]={5,6,3,8,2,12,0,1,4};//array d represent the time of de activity (v,u)
    int project_duration=0;//project duration


    /*# Compute the indegree for each vertex v from the graph:
    for each neighbor u of v: indegree[u] += 1*/
    for (j=0; j<numberActivities; j++){
        indegree[u[j]]++;
    }

    for (j=0;j<numberVertex; j++)
        printf ("indegree %d= %d\n",j,indegree[j] );

    queue<int> Q; //queue Q = empty queue
    int distance [numberVertex];
    memset(distance, 0, sizeof(int) * numberVertex);//distance = array filled with zeroes

    //for each vertex v:
    //if indegree[v] = 0:
    //insert v on Q
    for (j=0; j<numberVertex; j++)
    {
        if (indegree[j]==0)
            Q.push(v[j]);
    }

    int first;

    //printf ("first in the queue=%d\n", Q.front());

    /*for each neighbor u of v:
    d istance[u] = max(distance[u], distance[v] + time(v, u))
    indegree[u] -= 1
    if indegree[u] = 0:
    insert u on Q
    */
    while (!Q.empty()){ //while Q is not empty:
        first= Q.front ();  //v = get front element from Q
        Q.pop(); //delete de first from queue
        distance[u[first]]=std::max(distance[u[first]],
            distance[v[first]]+ d[first]);
        indegree[u[first]]-=1;

        if (indegree[u[first]]==0){

            Q.push(u[first]);
        }
    }



    for (j=0; j<numberVertex; j++)
    {
        printf ("dist [%d]= %d\n", j, distance[j]);
    }
    /*Now, select the vertex x with the largest distance. 
    This is the minimum total project_duration.*/
    printf ("Total Project Duration %d\n", project_duration);


    return (0);

}

Какво правя погрешно или как може да реши кода, за да ми каже каква е продължителността на проекта (съответства на сумата от разстояния от критичния път)?. може да изчисли само разстоянието до първите 3 върха.


c++ path directed-acyclic-graphs graph-theory dynamic-programming
person franvergara66    schedule 21.05.2011    source източник
comment
Не ми трябва алтернативно решение, а само решение, базирано на моя код. (масиви y опашка)   -  person franvergara66    schedule 21.05.2011
comment
Ще получите повече резултати с правилен отстъп и изявление какво точно не е наред с кода. В момента просто изглежда небрежно.   -  person Adam    schedule 21.05.2011

Отговори (1)


arrow_upward
1
arrow_downward

Вашата опашка съдържа върхове. Вашите масиви u, v, d са индексирани по номера на ръбовете. Така че не можете да пишете

first = Q.front();
... u[first] ...

тъй като first е връх.

По-общо, вашият код ще бъде много по-лесен за четене (и грешката ще бъде по-очевидна), ако използвате смислени имена на променливи. first не е много ясен (първо какво?), а u, v, d също са доста загадъчни.

писане на нещо подобно

cur_vertex = todo.front()
distance[dest[cur_vertex]] = std::max(distance[dest[cur_vertex]], 
    distance[source[cur_vertex]]+ weight[cur_vertex]);

незабавно ще повдигне въпрос: източникът на връх, какво е това? (Тук използваме имена на променливи като заместител на правилната проверка на типа. ADA програмист би декларирал два различни цели числа, за да избегне объркването между номерата на върховете и ръбовете.)

Друг въпрос: къде отиде цикълът над наследниците на first? Това е в псевдокода, но не и във вашия източник.

person adl    schedule 21.05.2011