最早開始時間と最遅完了時刻を求めるプログラムをC言語で作成せよ、という

質問

最早開始時間と最遅完了時刻を求めるプログラムをC言語で作成せよ、というものを学校の課題でやっているのですがうまく行きません。どこがおかしいのでしょうか。
内容としてはアローダイアグラムで表される業務についてです。所要日数は画像で記しておきました。

#include <stdio.h>

int main()
{
int ES[7];//最早開始時刻
int LS[7];//最遅完了時刻
int i,j; //ループカウンタ
int tmp;
int node[7][7] = {
{-1,5,-1,-1,-1,-1,-1},//1
{-1,-1,5,3,-1,-1,-1},//2
{-1,-1,-1,10,-1,12,-1},//3
{-1,-1,-1,-1,3,-1,-1},//4
{-1,-1,-1,-1,-1,0,3},//5
{-1,-1,-1,-1,-1,-1,6},//6
{-1,-1,-1,-1,-1,-1,-1}//7
};

for(i = 0;i <7;i++){
ES[i] = 0;
LS[i] = 0;
}
//最早
for(j = 0;j <6;j++){
for(i = 0;i <6;i++){
if(node[i][j]==-1){
continue;
}else{
tmp = node[i][j]+ES[i];
if(ES[j+1]==0){
ES[j+1]=tmp;
}else{
if(ES[j+1]<tmp){
ES[j+1]=tmp;
}
}
}
}
}
printf("最早開始日\n");
for(i = 0;i <7;i++){
printf("[%2d] : %3d\n",i+1,ES[i]);
}
//最遅
LS[7] = ES[7];
for(i =6;i>-1;i--){
for(j =6;j>-1;j--){
if(node[i][j]==-1){
continue;
}else{
tmp = LS[j+1]-node[i][j];
if(LS[i]==0){
LS[i]=tmp;
}else{
if(LS[i]>tmp){
LS[i]=tmp;
}
}
}
}
}
printf("最遅完了日\n");
for(i = 0;i <7;i++){
printf("[%2d] : %3d\n",i+1,LS[i]);
}
return 0;
}

最早開始日
[ 1] : 0
[ 2] : 5
[ 3] : 10
[ 4] : 20
[ 5] : 23
[ 6] : 23
[ 7] : 29
最遅完了日
[ 1] : 0
[ 2] : 5
[ 3] : 10
[ 4] : 20
[ 5] : 23
[ 6] : 23
[ 7] : 29

となるはずが、

最早開始日
[ 1] : 0
[ 2] : 0
[ 3] : 5
[ 4] : 5
[ 5] : 15
[ 6] : 8
[ 7] : 17
最遅完了日
[ 1] : -18
[ 2] : -14
[ 3] : -13
[ 4] : -9
[ 5] : -3
[ 6] : -6
[ 7] : 17

となってしまいます。

回答No.3

kmee · ベストアンサー

最早開始日の定義を確認してみたら
結合点j での最早開始日は
ESj=max_i{ESi + Pij}
Pij: 結合点i→結合点jの所要時間

で、これを素直にプログラムにしたらその「正しい結果」になりました。

ESj=max_i{ESi+Pij]を計算するときに、
Pij=node[i][j], ESi=ES[i]
としているのに、
ESj=ES[j+1]
と jが変わってしまっているのが原因の一つです。

最遅完了日も同様です。

//最早
//i,jは全範囲
for(j = 0; j <7; j++) {
for(i = 0; i <7; i++) {
if(node[i][j]==-1) {
continue;
}
// contiuneしたら続きは実行しないのだから、elseは不要
tmp = node[i][j]+ES[i];
// tmp >= 0 だから、ES[j]=0のときは、必ずmax(ES[j],tmp)=tmpになる
if (ES[j]<tmp) {
ES[j]=tmp;
}
}
}

お礼

回答ありがとうございます。参考になりました。
あと、結果を表示するところが終了条件のiの値が１つ足りてなかったことにも気がつきました。
おかげさまで解決できました。ありがとうございました。

回答No.2

himajin100000

http://ideone.com/wyUBo

ふむ。

お礼

回答ありがとうございます。参考になりました。

回答No.1

asuncion

＞int ES[7];//最早開始時刻
＞int LS[7];//最遅完了時刻

この定義で

＞LS[7] = ES[7];
＞tmp = LS[j+1]-node[i][j];

これはまずいです（後の方は、jが6のとき）。
配列の定義範囲外の領域にアクセスしています。

お礼

回答ありがとうございます。
しかし回答を元にLS[7] = ES[7];をLS[6] = ES[6];に、for(j =6;j>-1;j--){をfor(j =5;j>-1;j--){に変えて再び実行しても正しい結果になりませんでした。