Technically a homework question, though the deadline is past due. For learning purposes only, I want to know what was wrong with my code when I submitted. It's a Traveling Salesperson Problem, and the code is complete for the most part. I just can't seem to find what's causing the segmentation fault even after attempting to debug with gdb. Something is supposed to be wrong with line 76, but I don't see how my arrays are messing up. I've looked through this code countless times, and I know I'm just missing something small. Any advice would be appreciated -I just don't want to end up making whatever mistake I made on this again in the future.
Code:
#include <stdio.h>
#include <stdlib.h>
#define SIZE 20
int adjacency[SIZE][SIZE];
int best_cost;
int *BestList;
int permutations = 0;
void print_tour(int[],int,int);
main()
{
int best_cost;
void print_tour();
void permute_list();
int i,j,weight,num;
int *NodeList;
char c;
int cost;
int thisCost;
for( i = 0; i < SIZE; i++ )
for( j = 0; j < SIZE; j++ )
adjacency[i][j] = -1;
while( scanf("%c",&c) != EOF ) // Read input and build adjacency matrix
{
if( c == 'c' )
{
scanf("%d",&num);
}
else if( c == 'a' )
{
scanf("%d%d%d",&i,&j,&weight);
adjacency[i][j] = weight;
adjacency[j][i] = weight;
}
}
NodeList = (int *) malloc(num * sizeof(int));
BestList = (int *) malloc(num * sizeof(int));
for( i = 0; i < num; i++ )
{
NodeList[i] = i + 1;
BestList[i] = i + 1;
}
best_cost = 1000000000;
permute_list(NodeList,num,num);
print_tour(BestList,num,best_cost); // printf("After checking %d permutations,\n",permutations);
}
void permute_list(A,num,n)
int A[],num,n;
{
int i,j,temp;
int cost;
int start = n - num + 1; // if you want to "set" the first city.
// int start = n - num; // if you want to try ALL permutations
if( num == 1 )
{
cost = compute_cost(A,n);
if( cost < best_cost )
{
int k;
best_cost = cost;
for(k = 0; k < n; k++)
BestList[k] = A[k];
}
return;
}
for(i = start; i < n; i++)
{
permute_list(A,num-1,n);
temp = A[n-1]; //rotate the list
for( j = n-1; j > start; j-- )
{
A[j] = A[j-1];
}
A[start] = temp;
}
}
int compute_cost(List,num)
int List[],num;
{
int cost = 0;
int i;
for(i = 0; i < num-1; i++);
cost += adjacency
[List[i]]
[List[i+1]]; //permutations++;
cost += adjacency
[List[i]]
[List[0]]; //print_tour(List,num,cost);
return cost;
}
void print_tour(List,num,cost)
int List[],num,cost;
{
int i;
printf("The tour ");
for( i = 0; i < num; i++ )
printf("%d ", List[i]);
printf("%d ", List[0]);
printf(" costs %d\n",cost);
}
/*The tour 1 9 10 5 6 7 3 2 4 8 1 costs 2000*/