2

別の投稿のこのアルゴリズムに従って、画像の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つの頂点までの距離しか計算できません。

4

1 に答える 1

1

キューには頂点が含まれています。配列u、、、はエッジ番号vでdインデックス付けされます。だからあなたは書くことができません

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

firstは頂点なので。

より一般的には、意味のある変数名を使用すると、コードがはるかに読みやすくなります（そしてバグがより明白になります）。 firstあまり明確ではありません（最初は何ですか？）、そして、、uもかなり不可解です。vd

のようなものを書く

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

すぐに質問が発生します：頂点のソース、それは何ですか？ （ここでは、適切な型チェックの代わりに変数名を使用しています。ADAプログラマーは、頂点とエッジ番号の混同を避けるために、2つの異なる整数型を宣言します。）

別の質問：goの後継者のループはどこにありましたfirstか？これは擬似コードにありますが、ソースにはありません。

于 2011-05-21T10:54:33.777 に答える