在C++中計算DAG的關鍵路徑

Question

根據this algorithm的另一篇文章，我正在計算圖像的DAG的關鍵路徑。我的老師需要實現aarray，我簡化了作業說明，一個通過數組實現的簡單圖形。

此ES我的代碼，其中我有3個陣列V，U和d，分別代表邊緣的起源節點，所述邊緣的端節點和每對頂點之間的距離，如圖所示在上面的圖片中。在圖像的圖形中，項目的持續時間等於25，對應於距關鍵路徑的距離之和。

我的代碼無法根據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); 

} 

的僞代碼是什麼我做錯了，或者它是如何解決的代碼，告訴我什麼是該項目的持續時間（好好距離的計算對應於距關鍵路徑的距離的總和）。只能計算到第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的繼任者去？它在僞代碼中，但不在源代碼中。