我正在计算图像的DAG的关键路径,根据这个算法在另一篇文章中。我的老师要求实现aarray,我简化了作业语句,通过数组实现的简单图形。
这是我的代码,其中我有 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 个顶点的距离。