Ford-Fulkersonを実装している関数のセグメンテーションフォルト

Question

私はクラスの割り当てに取り組んでいます。私は把握できなかった問題にぶつかってきました。私は最大フローを見つけるためにBFSを使ってFord-Fulkersonアルゴリズムを実装しています。しかし、私の残存容量マトリックスを所定の容量に設定しようとしている間に、私はセグメント化エラーを起こしました。私たちが受け取ったテストコードでは、元の容量マトリックスがそのアドレスによって値渡されたことがわかりましたが、私のコードで私が私の考え方とやり取りしていないと感じていますか？それで私は他の場所で同じ問題が繰り返されるかもしれないと私に信じさせます。私は、GDBで働いていたと私はここでループのための私のネストされたこの行にセグメンテーションフォールトを打つことを見た：

resCap[i][j] = *(capacity + i*n + j); 

をので、私はかなり困惑していますけれどもしかし、私が試してみました何が私のために働いていません。

void maximum_flow(int n, int s, int t, int *capacity, int *flow) 
{ 
    int i, j, resCap[n][n], path[n]; // residual capacity and BFS augmenting path 
    int min_path = INT_MAX; // min of the augmenting path 

    // Assign residual capacity equal to the given capacity 
    for (i = 0; i < n; i++) 
     for (j = 0; j < n; j++) 
     { 
      resCap[i][j] = *(capacity + i*n + j); 
      *(flow + i*n + j) = 0; // no initial flow 
     } 

    // Augment path with BFS from source to sink 
    while (bfs(n, s, t, &(resCap[0][0]), path)) 
    { 
     // find min of the augmenting path 
     for (j = t; j != s; j = path[j]) 
     { 
      i = path[j]; 
      min_path = min(min_path, resCap[i][j]); 
     } 

     // update residual capacities and flows on both directions 
     for (j = t; j != s; j = path[j]) 
     { 
      i = path[j]; 
      if(*(capacity + i*n + j) > 0) 
      *(flow + i*n + j) += min_flow_path; 
      else 
      *(flow + j*n + i) -= min_flow_path; 

      resCap[i][j] -= min_flow_path; 
      resCap[j][i] += min_flow_path; 
     } 
    } 
} 

そしてここにそれが必要とされる場合には、私たちに与えられたテストコードです：

int main(void) 
{ int cap[1000][1000], flow[1000][1000]; 
    int i,j, flowsum; 
    for(i=0; i< 1000; i++) 
    for(j =0; j< 1000; j++) 
     cap[i][j] = 0; 

    for(i=0; i<499; i++) 
    for(j=i+1; j<500; j++) 
     cap[i][j] = 2; 
    for(i=1; i<500; i++) 
    cap[i][500 + (i/2)] =4; 
    for(i=500; i < 750; i++) 
    { cap[i][i-250]=3; 
    cap[i][750] = 1; 
    cap[i][751] = 1; 
    cap[i][752] = 5; 
    } 
    cap[751][753] = 5; 
    cap[752][753] = 5; 
    cap[753][750] = 20; 
    for(i=754; i< 999; i++) 
    { cap[753][i]=1; 
     cap[i][500]=3; 
     cap[i][498]=5; 
     cap[i][1] = 100; 
    } 
    cap[900][999] = 1; 
    cap[910][999] = 1; 
    cap[920][999] = 1; 
    cap[930][999] = 1; 
    cap[940][999] = 1; 
    cap[950][999] = 1; 
    cap[960][999] = 1; 
    cap[970][999] = 1; 
    cap[980][999] = 1; 
    cap[990][999] = 1; 
    printf("prepared capacity matrix, now executing maxflow code\n"); 
    maximum_flow(1000,0,999,&(cap[0][0]),&(flow[0][0])); 
    for(i=0; i<=999; i++) 
    for(j=0; j<=999; j++) 
    { if(flow[i][j] > cap[i][j]) 
     { printf("Capacity violated\n"); exit(0);} 
    }  
    flowsum = 0; 
    for(i=0; i<=999; i++) 
    flowsum += flow[0][i]; 
    printf("Outflow of 0 is %d, should be 10\n", flowsum); 
    flowsum = 0; 
    for(i=0; i<=999; i++) 
    flowsum += flow[i][999]; 
    printf("Inflow of 999 is %d, should be 10\n", flowsum); 

    printf("End Test\n"); 
} 

Answer 1

この行は、おそらくセグメンテーションフォールトしようとしている、それはクランを使用して行います。

int i, j, resCap[n][n], path[n]; 

スタック上に非常に大きな配列が宣言されています。あなたがcallocを使ってそれを割り当てようとすると、どれくらい大きなものが見えますか？代わりにこれを試してみて、同じ種類のループを使ってfreeに忘れないようにしてください。

int **resCap2 = calloc(1, n * sizeof(int *)); 
assert(resCap2); 
for (i = 0; i < n; i++) { 
    resCap2[i] = calloc(1, n * sizeof(int)); 
    assert(resCap2[i]); 
} 

これは、デバッガを使用して、または中間ステップを印刷

(1000 * sizeof(int*) * (1000 * n * sizeof(int)))