Вычисление критического пути DAG в C ++

Question

Я делаю расчет критического пути для 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 вершин.

Answer 1

Ваша очередь содержит вершины.Ваши массивы 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?Это в псевдокоде, но не в вашем источнике.