Я работаю над назначением класса, и у меня возникла проблема, которую я не смог выяснить. Я использую алгоритм Форда-Фулкерсона, используя BFS, чтобы найти максимальный поток. Но при попытке установить мою матрицу остаточной емкости на заданную емкость я ударил ошибку сегментации. В тестовом коде, который мы получили, я вижу, что исходная матрица емкости передавалась по значению по ее адресу, но я чувствую, что в своем коде я не взаимодействую с ней, как я думаю, что я? Это заставляет меня поверить, что у меня может быть одна и та же проблема, повторяющаяся в другом месте. Я работал с БГД и увидел, что я ударил ошибку сегментации на этой линии здесь в моем вложенной цикл:Ошибка сегментации в функции, реализующей Ford-Fulkerson
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");
}
Использование отладчика, или печать промежуточных шагов, проверьте на какой линии вы получите ошибку сегментации. Этот процесс называется отладкой. Если вы не знаете, как отлаживать свой код, ваши другие навыки программирования не полезны. – user31264
Извините! Я забыл упомянуть в своем посте, что я использовал gdb, чтобы найти, где моя ошибка сегментации, я ударил ее по строке «resCap [i] [j] = * (capacity + i * n + j)»; Я считаю, что моя проблема заключается в том, как я копирую исходную матрицу производительности в свою матрицу остаточной емкости, однако ничто из этого не кажется правильным. –
напечатайте 'i' на каждой итерации цикла. Вы узнаете, в чем «вы получаете ошибку сегментации. то для этого 'i' напечатайте' j' на каждой итерации самого внутреннего цикла. – user31264