计算 C++ 中 DAG 的关键路径;
我正在计算图像 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.
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 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
您的队列包含顶点。您的数组
u
、v
、d
通过边数进行索引。所以你不能写,
因为
first
是一个顶点。更一般地说,如果您使用有意义的变量名称,您的代码将更容易阅读(并且错误将更明显)。
first
不是很明确(first 什么?),而u
、v
、d
也相当神秘。写类似的东西
会立即提出一个问题:顶点的源,那是什么?
(这里我们使用变量名来代替正确的类型检查。ADA 程序员会声明两种不同的整数类型,以避免顶点和边数之间的混淆。)
另一个问题:
的后继者的循环在哪里首先
去吗?它在伪代码中,但不在您的源代码中。Your queue contains vertices. Your arrays
u
,v
,d
, are indexed by edge numbers.So you cannot write
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?), andu
,v
,d
are also quite cryptic.writing something like
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.