计算 C++ 中 DAG 的关键路径;

发布于 2024-11-09 04:49:36 字数 2845 浏览 10 评论 0原文

我正在计算图像 DAG 的关键路径,根据 这个算法为另一篇文章。我的老师要求实现一个数组,我简化了作业语句,通过数组实现了一个简单的图。

在此处输入图像描述

这是我的代码,其中我有 3 个数组 v、u 和 d,代表边、边的结束节点以及每对顶点之间的距离,如上图所示。在图像图中,项目的持续时间等于 25,对应于距关键路径的距离之和。

我的代码无法根据此链接<的伪代码很好地计算距离/a>

#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 个顶点的距离。

I'm doing the calculation of the critical path for the DAG of the image, according to this algorithm for another post.My teacher requires that aarray be implemented, I simplify the homework statement, a simple graph implemented through arrays.

enter image description here

This es my code in which I have 3 arrays v, u and d, representing the origin node of the edges, the end node of the edges and the distance between each pair of vertices, as shown in the picture above. in the graph of the image, the duration of the project is equal to 25 corresponding to the sum of distances from the critical path.

My code fails to make good the calculation of distances according to the pseudocode of this link

#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);

}

What am I doing wrong or how it could solve the code to tell me what is the duration of the project (corresponds to the sum of distances from the critical path)?. only able to calculate the distance to the first 3 vertex.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

做个少女永远怀春 2024-11-16 04:49:36

您的队列包含顶点。您的数组 uvd 通过边数进行索引。
所以你不能写,

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

因为 first 是一个顶点。

更一般地说,如果您使用有意义的变量名称,您的代码将更容易阅读(并且错误将更明显)。 first 不是很明确(first 什么?),而 uvd 也相当神秘。

写类似的东西

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

会立即提出一个问题:顶点的源,那是什么?
(这里我们使用变量名来代替正确的类型检查。ADA 程序员会声明两种不同的整数类型,以避免顶点和边数之间的混淆。)

另一个问题:的后继者的循环在哪里首先 去吗?它在伪代码中,但不在您的源代码中。

Your queue contains vertices. Your arrays u, v, d, are indexed by edge numbers.
So you cannot write

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

since first is a vertex.

More generally, your code will be a lot easier to read (and the bug will be more obvious) if you use meaningful variable names. first is not very explicit (first what?), and u, v, d are also quite cryptic.

writing something like

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

will immediately raise a question: the source of a vertex, what is that?
(Here we are using variable names as a substitute for proper type checking. An ADA programmer would have declared two different integer types to avoid the confusion between vertices and edge numbers.)

Another question: where did the loop over the successors of first go? It's in the pseudo-code, but not in your source.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文